NOIP '18 P2 - Currency System

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

In a coin system , there are coins of different values. The -th coin in the system has value , and you may assume each kind of coin has unlimited supply. Now you are given a coin system , and you need to find an equivalent coin system such that is minimized (i.e. the coin system having the minimum number of denominations). Here, "equivalent" means for any nonnegative value , can be expressed in one currency system if and only if it can be expressed in the other currency system.

Input Specification

The first line contains an integer denoting the number of test cases.

For each test case, the first line contains an integer . In the following line, there are space-separated integers denoting the values of the coins in the coin system.

Output Specification

The output contains lines. For each test case, output a line containing an integer denoting the minimum such that is equivalent to coin system .

2
4
3 19 10 6
5
11 29 13 19 17

2
5

Explanation

In the first test case, the currency system is equivalent to the given currency system, and it is easy to see there are no equivalent currency systems with . As a result, the answer is 2.

In the second test case, it can be shown that there does not exist any equivalent currency system with , so the answer is 5.

Additional samples can be found here.

Constraints

Test Case  1~3  4-6 7-8 9-10 11~13  14~16  17~20  For all test cases, , .