题目详情

秦始皇统一了六国, 他发现国家内有各种各样的货币, 每个货币有自己的价格代表了它的价值, 这太不方便了。 货币情况可以如下描述: 有种不同价格的货币，第 $i$ 种货币的价格是 $a[i]$，假定每一种货币都有无穷多个。注意, 即使两种货币的价格一样, 他们也是不同的货币. 为了方便统计，把货币种类定为 $n$ 、价格数组为 $a[1...n]$ 的货币系统记为 $(n,a)$ . 两个货币系统不同当且仅当n不同或者存在至少一种货币不同. 和货币系统内货币的排列顺序无关. 在秦始皇的认知里，每一个非负整数的价格都应该可以被表示出来；对每一个非负整数的价格，都存在个非负整数满足的和为. 但是，在目前这个世界，货币的价格管理系统可能是不完善的，可能存在价格不能被货币管理系统表示出来。例如：在货币管理系统, $n =3$ , $a = [2,5,9]$ 中，价格 $1 3$ 就无法被表示出来. 现在假定两个货币管理系统是等价的，当且仅当对于任意非负整数，要么都可以被两个货币系统表示出来，要么不能被任何一个表示出来。 现在秦始皇打算简化下货币管理系统, 他有两个问题: 1.他希望找到一个货币管理系统 $(p,c)$ ，满足 $(p,c)$ 与原来的货币管理系统等价，且尽可能的小。他希望你来告诉他最小的是多少. 2.满足第一条的货币管理系统有多少种不同的可能性, 答案对 $1e9+7$ 取模.

输入描述

第一行包含一个整数,表示数据组数。接下来按照如下格式分别给出组数据。 每组数据的第一行包含一个正整数。接下来一行包含个由空格隔开的正整数, 代表每个货币的价格。 输出描述 共行, 对于每组数据, 输出一行两个整数, 表示所有与等价的货币系统中, 最小的, 以及最小的对应的货币系统有多少种不同的可能. 输入样例 1

2
4
3 3 10 6
5
11 29 13 19 17

输出样例 1

2 2
5 1

输入样例2

2
5
6 5 5 6 8
9
12 25 16 11 18 20 14 15 25

输出样例2

3 4
7 1

样例解释 在第一组数据中，$(2,[3,10])$ 货币管理系统和给出的货币管理系统 $(n,a)$ 等价，并可以验证不存在 $p<2$ 的等价的货币管理系统，因此最小 $p$ 的为 $2$ 。第一个 $3$ 和第二个 $3$ 均可以完成 此系统, 一共两种, 无法找到更多. 在第二组数据中，可以验证不存在 $p<n$ 的等价的货币管理系统，因此答案为 $5$ 。只有一种.

数据范围

对于 $20$ 的数据， $n=2$ ； 对于 $60$ 的数据， $T == 1$ , $1≤n≤10$ ； 对于 $80$ 的数据， $T == 1$ , $1≤n≤20$ ； 对于 $100$ 的数据， $1≤T≤20$ , $1≤n≤100$ , $1≤a[i]≤25000$ ；