#### Catch The Frogs

**Author: ** Efat Sikder

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

**in order to catch all frogs that would ever pass through the corresponding coordinate.**

*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.

- The first line of each test case contains a single integer n
- the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.*(1 ≤ n ≤ 2 ⋅ 10*^{5}) - The second line of each test case contains
integers*n**A*_{i}- the lengths of the hops of the corresponding frogs.*(1 ≤ A*_{i }≤ 10^{9})

*It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^{5}*

#### Output Format

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

#### Samples

###### Input

###### Output

Language | Time | Memory |

GNU C 11 | 1s | 512MB |

GNU C++ 14 | 1s | 512MB |

GNU C++ 11 | 1s | 512MB |

PHP 7 | 1s | 1024MB |

Java (OpenJDK 8) | 1s | 4096MB |