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

$(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,...,$an

$(1<=$ai$<=109$

$)$ the elements of the array a

$.$

It is guaranteed that the sum of n

over all test cases does not exceed $2000$

$.$

Output