We have all heard about good triumphing over evil. A perfect example would be the Battle of Helms Deep.

Lets probe a little deeper...

The people (especially warriors) of Rohan (good side) could not have known that they would win the battle before it was actually fought. This would have forced them to think up of some other alternate means of escape. A river flows near the fortress and naturally, they think this to be the best escape route. They build the biggest ship possible with the available materials.

This ship can carry a total weight of W (0 < W < 10^9) kilograms. There are a total of n (0 < n < 10000) people at Helms Deep having weights wi (0 < wi < 10^9).

What is the maximum number of people who can escape?

Input

1st line contains t, the number of testcases. First line of each test case contains the number of people n(0

Output

One line giving the maximum number of people who can escape.

Example

Input:
1
3 3
2
1
3

Output:
2