LOTR1 - Helms Deep

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

Added by:pradeep
Date:2009-06-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Lord of the Rings (2 towers)

hide comments
2020-05-09 00:05:40
Beware of blanklines in input.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.