Mihai and Slavic, two curious children, were gazing at a group of frogs numbered from 1 to n. Each frog had a hop length of 1 to A_i.

The frogs were all initially located at point 0, and each second, frog i would hop A_i units forward. Before any frogs started hopping, Slavic and Mihai could place exactly one trap in a coordinate in order to catch all frogs that would ever pass through the corresponding coordinate.

However, the children couldn't go far away from their home, so they could only place a trap in the first n points (that is, in a point with a coordinate between 1 and n) and the children couldn't place a trap in point 0 since they were scared of frogs.

Slavic and Mihai wanted to catch as many frogs as possible, so they asked you for help. Can you help them find out what is the maximum number of frogs they can catch using a trap?

Input Format

The first line of the input contains a single integer t (1 < t < 100) - the number of test cases. The description of test cases follows.

1. The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10⁵) - the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.
2. The second line of each test case contains n integers A_i (1 ≤ A_i ≤ 10⁹) - the lengths of the hops of the corresponding frogs.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10⁵

Output Format

For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.

Samples