A gang of *n* vicious drug dealers is surrounding Walker, the world’s favourite
Texas ranger. But do not worry! This would be a critical situation for most
people, but not for Walker. He can hit all of them with just a single of his
“spinning kicks”.

However, as this is a TV series, the co-guionist Aaron Norris has reminded his brother (the great actor Chuck Norris starring as Walker) that he should take care of several restrictions:

- Drug dealers can only be hitted increasingly, from drug dealer 1 to drug
dealer
*n*. (This is because of the location of the camera.) - Walker can only hit each drug dealer
*i*at some specific time*t*_{i}known in advance. (This is due to the insurance that any actor working with Chuck has to take.) Therefore, Walker cannot hit two drug dealers*i*<*j*such that*t*_{i}>*t*_{j}with the same spinning kick. - The time between two hits should be at least 10 ms. (Even a slow
motion camera cannot properly film Chuck’s kicks if they are too
quick.) This implies that Walker cannot hit with the same kick two drug dealers
*i*<*j*such that*t*_{j}−*t*_{i}< 10 ms.

– “We must follow these rules, Chuck”, Aaron says. “I’m sure it’s not hard for you to find the maximum number of guys you can hit with a single spinning kick under these restrictions.”

– “Indeed, it is not”, Chuck replies after thinking for a couple of microseconds.

– “Then, Chuck, please, follow these rules. Do it for the kids, Chuck!”

– “Alright.”

Can you write a program to compute the maximum number of drug dealers that Chuck can hit with a single spinning kick under the given restrictions?

**Input**

Input begins with a number *t* ≥ 0. Follow *t*
test cases, each with the number 0 < *n* ≤ 2000 of drug
dealers, followed by *t*_{1}, …, *t*_{n} in ms. Each *t*_{i} satisfies 0
≤ *t*_{i} ≤ 10^{9}. (Chuck can really give such loooong spinning kicks.
Indeed, he is a 6-time Karate World Champion!)

**Output**

Print *t* lines with the answers.

**Observation**

Due to his Cherokee upbringing,
Chuck can solve this problem in Θ(*n* log*n*) time.
But *you* may be not as good a programmer as Chuck,
so the Judge will accept quadratic solutions.

Public test cases

**Input**

6 2 2000 2010 3 7000 7009 7018 4 8000 7000 6000 5000 1 100 10 0 11 45 23 30 48 19 11 60 73 13 84 85 94 105 45 107 32 68 45 109 67 77 120

**Output**

2 2 1 1 6 5

Information

- Author
- Omer Gimémez
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Cinquè Concurs de Programació de la UPC - SemiFinal
- Date
- 2007-09-19