#591 Mochi

Statement

Statement language

You are given $N$ rice cakes. The size of the $i$ -th rice cake is $A_i$ .

You may choose two unused rice cakes and make one bundle. The rice cake placed on top must be strictly larger than the one placed below. A rice cake cannot be used in more than one bundle.

Find the maximum number of bundles that can be made.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the maximum number of bundles.

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	7	$N \leq 10$ . The sum of $N$ over all test cases does not exceed $2\,000$ .
2	14	$A_{1}, A_{2}, \dots$ are pairwise distinct.

Samples

Input

1
7
1 1 2 2 3 3 3

Output

3

Pairing rice cakes with sizes $(1,2)$ , $(1,3)$ , and $(2,3)$ creates three bundles. The one remaining rice cake cannot form another bundle, so the maximum number is $3$ .