B. OverCode
time limit per test
1 second
memory limit per test
256 megabytes
input
overcode.in
output
standard output

In a competitive coding contest called OverCode, matches are held between two teams. Each team must have exactly 6 coders. In order to form fair matches between coders, the absolute difference between the ratings of any two members of the same team shouldn't exceed 1000.

What is the maximum number of teams that can be formed out of n coders if you were given their ratings, such that each coder is a member of at most one team?

Input

The first line of input contains a single integer T (1 ≤ T ≤ 512), the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 500), the number of coders participating in OverCode.

The next line contains n space-separated integers r1, r2, ..., rn (1 ≤ ri ≤ 4000), ri is the rating of the ith coder.

The total sum of n overall test cases doesn't exceed 1.5 × 105.

Output

For each test case, print the maximum number of teams that can be formed, on a single line.

Example
Input
3
5
4 1 5 3 2
6
1 1001 2 4 3 5
13
7 9 7 2 1000 1001 2 3 9 4 5 2 5
Output
0
1
2