I. Leah's Grand Team Formation (Black)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In preparation for the next Grand Prix, racers are forming teams.

Each racer has a rating. Leah, the one managing the race has one rule for team formation:

If a racer's rating is greater than or equal to 1500, they compete in the Grand Prix solo. Otherwise, they must form teams of up to 3 members.

Teams

Given the rating scores of all racers, determine the minimum total number of teams required for the Grand Prix.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of racers.

The second line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$100 \le r_i \le 3500$$$) — where $$$r_i$$$ is the rating score of the $$$i$$$-th racer.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$

Output

Output $$$t$$$ integer representing the minimum total number of teams for each test case.

Example
Input
3
4
1339 1664 1414 1632
3
1000 1000 1000
5
1600 1400 1200 1700 1500
Output
3
1
4