# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Meera bought candies from the store. She is now going to distribute those among her **N** friends. She makes her friends stand in a line. Then, she chooses an array **A** of length **K** containing positive integers.

The candy distribution has **K** phases. At phase **i**, she takes the array element **A[i]** and starts giving candies to person **A[i], 2 *A[i], 3*A[i],…, floor(N/A[i])*A[i]**.

For example, if **N** is **10** and the array is **{ 2,3,5}**. Then at first phase people at **{ 2,4,6,8,10}** gets candy. At second phase, **{ 3,6,9}** gets candy. And at last phase **{ 5,10}** gets candy.

Now notice that some people got more than one candy, some none at all and some got exactly one candy. Meera wants to find out how many people got exactly one candy. Can you help her?

The first line of the input will contain a single integer **T**, which is number of test case.

The first line of each case will contain two positive integers, **N** and **K**. On the second line of the test case, there will be **K** positive integers denoting the array **A**.

**T <= 50**

**N <= 10^{18}**

**K <= 18**

**A[i] <= 10^{18}**

For each test case, print a single integer which is the number of people who got exactly one chocolate.

Input | Output |
---|---|

2 10 3 2 3 5 20 3 2 3 7 | 6 10 |

20% Solution Ratio

tasmeemrezaEarliest,

turab_Fastest, 696059.8s

Matrix.codeLightest, 262 kB

Bishal_GShortest, 736B

Login to submit

NSU Code Masters 2016 Ended |

Replay of NSU Code Masters 2016 Ended |