404678: GYM101608 B OverCode

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. OverCodetime limit per test1 secondmemory limit per test256 megabytesinputovercode.inoutputstandard 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.

ExampleInput
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

加入题单

上一题 下一题 算法标签: