In the country of Netizens, there are $n$ different denominations of currency. The denomination of the $i$-th currency is $a[i]$. You may assume that there is an infinite supply of each currency. For convenience, we denote a currency system with $n$ types of currency and denominations $a[1..n]$ as $(n, a)$.

In a perfect currency system, every non-negative amount $x$ should be representable, meaning that for every non-negative integer $x$, there exist $n$ non-negative integers $t[i]$ such that the sum $\sum_{i=1}^n a[i] \times t[i]$ equals $x$. However, in the country of Netizens, a currency system might be imperfect, meaning there may exist amounts $x$ that cannot be represented by the currency system. For example, in the currency system $n=3, a=[2, 5, 9]$, the amounts $1$ and $3$ cannot be represented.

Two currency systems $(n, a)$ and $(m, b)$ are equivalent if and only if for any non-negative integer $x$, either both currency systems can represent $x$, or neither of them can represent $x$.

Now, the Netizens intend to simplify their currency system. They hope to find a currency system $(m, b)$ that is equivalent to the original currency system $(n, a)$, and where $m$ is as small as possible. You are asked to assist them in this difficult task: find the minimum $m$.

Input

The first line contains a single integer $T$, representing the number of test cases. Then, $T$ test cases are provided according to the following format:

Each test case starts with a positive integer $n$. The next line contains $n$ space-separated positive integers $a[i]$.

Output

For each test case, output a single line containing a positive integer, representing the minimum $m$ among all currency systems $(m, b)$ that are equivalent to $(n, a)$.

Examples

Input 1

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

Output 1

2
5

Note 1

In the first test case, the currency system $(2, [3, 10])$ is equivalent to the given currency system $(n, a)$, and it can be verified that there is no equivalent currency system with $m < 2$, so the answer is $2$.

In the second test case, it can be verified that there is no equivalent currency system with $m < n$, so the answer is $5$.

Constraints

For 100% of the data, $1 \le T \le 20$, $n, a[i] \ge 1$.