Do it for the kids, Chuck!

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 \ge 0$ . Follow $t$ test cases, each with the number $0 < n \le 2000$ of drug dealers, followed by $t_1, \ldots, t_n$ in ms. Each $t_i$ satisfies $0 \leq t_i \leq 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 $\Theta(n \log n)$ time. But you may be not as good a programmer as Chuck, so the Judge will accept quadratic solutions.

Problem information

Author: Omer Gimémez

Generation: 2026-01-25T10:26:27.316Z