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.

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\).

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.

提交代码