M. Tardi's and Sami's Ten Little Monkeys
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ beds perfectly aligned in a row, numbered from $$$1$$$ to $$$n$$$.You are taking care of $$$m$$$ monkeys.

Each monkey has a specific jump power, where the $$$i$$$-th monkey has a jump power of $$$a_i$$$. All monkeys start on the floor at position $$$0$$$ (strictly before the first bed).

You can allow the monkeys to jump on the beds one by one, in any order you choose. When the $$$i$$$-th monkey is allowed to jump, it will take leaps of exactly $$$a_i$$$ distance forward. This means the monkey will land on bed $$$a_i$$$, then bed $$$2a_i$$$, then bed $$$3a_i$$$, and so on, until it jumps past the $$$n$$$-th bed.

The beds are fragile. If any monkey lands on a bed, the bed instantly breaks. Once a bed is broken, it remains broken. Multiple monkeys can land on the same broken bed.Determine the total number of beds that will be broken after you let all $$$m$$$ monkeys jump.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of beds and the number of monkeys.

The second line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$2 \le a_i \le n$$$) — the jump power of each monkey.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the total number of broken beds.

Example
Input
4
10 2
4 6
5 3
2 3 4
100 1
50
6 4
2 2 2 2
Output
3
3
2
3