Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RTF - Cân thăng bằng

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/rtf


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

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-08-10
Thời gian chạy:1s
Giới hạn mã nguồn:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2015-11-02 06:38:45
Bài này hình như có test a[i] > 60000.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.