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 25000$

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