Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3997
Seat Assignment

Time Limit: 2 Seconds      Memory Limit: 65536 KB

People in Wonderland love watching movies. Recently, a very popular movie called Despicable Me 3 is on show and people can't wait to enjoy it in the cinema. Obviously, everyone loves to take a seat in the row that is neither too far nor too near from the screen.

You are the manager of a local cinema. Today, you have received many requests to book seats in a certain row. For convenience, let's number the seats in that row from 1 to \(M\). People in Wonderland are crazy about maths, so they just want their seat number to be a multiple of a certain number. Each seat can only be taken by at most one person. You have known that for \(i\) from 1 to 10, there are \(A_i\) people wanting their seat numbers to be a multiple of \(i\). You task is to make full use of your math skills to satisfy as many people as possible.

Input

The first line contains a single interger \(T\) (about \(10^4\)), indicating the number of test cases. For each test case:

The first line contains a positive interger \(M\) (\(1 \le M \le 10^9\)), indicating the number of seats in the row.

the second line contains 10 integers \(A_1, A_2, \dots, A_{10}\) (\(0 \le A_i \le 10^9\)), indicating that there are \(A_i\) people wanting their seat numbers to be a multiple of \(i\).

Output

For each case output one integer, indicating the maximum number of requests you can satisfy.

Sample Input

2
10
2 1 4 0 0 0 0 0 0 0
6
0 2 0 1 0 0 0 0 0 0

Sample Output

6
3

Hint

The first sample:
There are 10 seats numbered from 1 to 10.
There are 2 people wanting their seat number to be a multiple of 1, 1 person wanting his seat number to be a multiple of 2, and 4 people wanting their seat number to be a multiple of 3.
The 2 people wanting their seat number to be a multiple of 1 can take seats numbered 1 and 4.
The only person wanting his seat number to be a multiple of 2 can take seat numbered 2.
The 3 people wanting their seat number to be a multiple of 2 can take seats numbered 3, 6, 9.

The second sampleļ¼š
The 2 people wanting their seat number to be a multiple of 2 can take seats numbered 2, 6.
The only person wanting his seat number to be a multiple of 4 can take seat numbered 4.


Author: LIU, Zhenwei
Source: ZOJ Monthly, January 2018
Submit    Status