In a coin system ~(n,a)~, there are coins of ~n~ different values. The ~i~-th coin in the system has value ~a_i~, and you may assume each kind of coin has unlimited supply. Now you are given a coin system ~(n,a)~, and you need to find an equivalent coin system ~(m,b)~ such that ~m~ is minimized (i.e. the coin system having the minimum number of denominations). Here, "equivalent" means for any nonnegative value ~x~, ~x~ can be expressed in one currency system if and only if it can be expressed in the other currency system.

Input Specification

The first line contains an integer ~T~ denoting the number of test cases.

For each test case, the first line contains an integer ~n~. In the following line, there are ~n~ space-separated integers ~a_i~ denoting the values of the coins in the coin system.

Output Specification

The output contains ~T~ lines. For each test case, output a line containing an integer denoting the minimum ~m~ such that ~(m,b)~ is equivalent to coin system ~(n,a)~.

Sample Input 1

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

Sample Output 1

2
5

Explanation

In the first test case, the currency system ~(2,[3,10])~ is equivalent to the given currency system, and it is easy to see there are no equivalent currency systems with ~m < 2~. As a result, the answer is 2.

In the second test case, it can be shown that there does not exist any equivalent currency system with ~m < n~, so the answer is 5.

Additional Samples

Additional samples can be found here.

Constraints

Test Case	~n~	~a_i~
1~3	~=2~	~\le 1000~
4-6	~=3~
7-8	~=4~
9-10	~=5~
11~13	~\le 13~	~\le 16~
14~16	~\le 25~	~\le 40~
17~20	~\le 100~	~\le 25\,000~

For all test cases, ~1 \le T \le 20~, ~n, a_i \ge 1~.