## 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, , .