Giải bài trực tuyến

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[i1] , A[i2] , … A[ik] 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[i1] * H[1][1] + … + A[ik] * H[1][k]
A[2] = A[i1] * H[2][1] + … + A[ik] * H[2][k]
…
A[N] = A[i1] * H[N][1] + … + A[ik]* 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 ≤ T ≤ 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 ≤ 100 ) .
Dòng 2 : N số nguyên dương A[1] , … , A[N] ( A[i] ≤ 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 .

Example

Input:
1
3
2 3 4

Output:
2