Có ~1~ bộ ~N~ loại quả cân, loại quả ~i~ nặng ~A_i~ kg. Một bộ con của bộ ~N~ quả cân gồm ~k~ loại quả cân là ~A_1~, ~A_2~, ...~A_k~ gọi là thay thế được bộ ~N~ loại quả cân trên nếu như tồn tại hệ đẳng thức sau:

• ~A_1 = A_1 \times H_{1, 1} + \dots + A_k \times H_{1, k}~
• ~A_2 = A_1 \times H_{2, 1} + \dots + A_k \times H_{2, k}~
• ...
• ~A_N = A_1 \times H_{N, 1} + \dots + A_k \times H_{N, k}~

Trong đó ~H_{i, j}~ là các số nguyên.

Hãy tìm bộ quả cân thay thế được cho bộ ~N~ quả cân với số phần tử là nhỏ nhất.

Input

Dòng ~1~ là số nguyên ~T~ là số bộ test ~(1 \leq T \leq 100)~. Các dòng tiếp theo mô tả ~T~ bộ test, mỗi bộ test gồm ~2~ dòng:

Dòng ~1~: Số nguyên dương ~N~ ~(N \leq 100)~.

Dòng ~2~: ~N~ số nguyên dương ~A_1~, ..., ~A_N~ ~(A_i \leq 60000)~

Output

Với mỗi bộ test ghi ra 1 số nguyên dương là số lượng quả cân của nhóm tìm được .

Sample Input

1
3
2 3 4

Sample Output

2