404678: GYM101608 B OverCode

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?

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 r₁, r₂, ..., r_n (1 ≤ r_i ≤ 4000), r_i is the rating of the i^th coder.

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

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

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

0
1
2