Bears were learning about rectangles! They have found that a set of M rectangles is called nestable, if

• All of them have integer height and width.
• There exists an ordering of them so that i-th rectangle’s height is strictly less than (i+1)-th rectangle's height and i-th rectangle’s width is strictly less than (i+1)-th rectangle’s width, for i=1, 2,.., M-1.

Do you remember the array A of N integers you have found last night? For each i = 1, 2, ..., N, you are allowed to make at most one rectangle with area exactly A_i.

You are given the array A. What is the maximum number of rectangles you can make so that the Bears call them nestable?

The first line will contain a single integer T (1 ≤ T ≤ 10⁵). Each test case will have a single integer N (1 ≤ N ≤ 10⁵), denoting the size of the block. The following line will have N integers separated by spaces, denoting array A (1 ≤ A_i ≤ N).

Sum of N over all cases does not exceed 6 x 10⁵.

For each test case, print a line containing the case number and the answer.