In a coin system , there are coins of different values. The -th coin in the system has value , and you may assume each kind of coin has unlimited supply. Now you are given a coin system , and you need to find an equivalent coin system such that is minimized (i.e. the coin system having the minimum number of denominations). Here, "equivalent" means for any nonnegative value , 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 denoting the number of test cases.

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

#### Output Specification

The output contains lines. For each test case, output a line containing an integer denoting the minimum such that is equivalent to coin system .

#### 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 is equivalent to the given currency system, and it is easy to see there are no equivalent currency systems with . 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 , so the answer is 5.

#### Additional Samples

Additional samples can be found here.

#### Constraints

Test Case | ||
---|---|---|

1~3 | ||

4-6 | ||

7-8 | ||

9-10 | ||

11~13 | ||

14~16 | ||

17~20 |

For all test cases, , .

## Comments