Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Nikita and LCM
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nikita is a student passionate about number theory and algorithms. He faces an interesting problem related to an array of numbers.

Suppose Nikita has an array of integers a of length n. He will call a subsequence of the array special if its least common multiple (LCM) is not contained in a. The LCM of an empty subsequence is equal to 0.

Nikita wonders: what is the length of the longest special subsequence of a? Help him answer this question!

A sequence b is a subsequence of a if b can be obtained from a by the deletion of several (possibly, zero or all) elements, without changing the order of the remaining elements. For example, [5,2,3] is a subsequence of [1,5,7,8,2,4,3].

Input

Each test contains multiple test cases. The first line of input contains a single integer t (1t2000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1n2000) — the length of the array a.

The second line of each test case contains n integers a1,a2,,an (1ai109) — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2000.

Output

For each test case, output a single integer — the length of the longest special subsequence of a.

Example
Input
6
5
1 2 4 8 16
6
3 2 10 20 60 1
7
2 3 4 6 12 100003 1200036
9
2 42 7 3 6 7 7 1 6
8
4 99 57 179 10203 2 11 40812
1
1
Output
0
4
4
5
8
0
Note

In the first test case, the LCM of any non-empty subsequence is contained in a, so the answer is 0.

In the second test case, we can take the subsequence [3,2,10,1], its LCM is equal to 30, which is not contained in a.

In the third test case, we can take the subsequence [2,3,6,100003], its LCM is equal to 600018, which is not contained in a.