write a go solution for Description:
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^dagger 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!

^dagger 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 Format:
Each test contains multiple test cases. The first line of input contains a single integer t (1<=t<=2000) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains n integers a_1,a_2,ldots,a_n (1<=a_i<=10^9) — the elements of the array a.

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

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

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,100,003], its LCM is equal to 600,018, which is not contained in a.. Output only the code with no comments, explanation, or additional text.