Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

B. Collecting Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a of n positive integers and a score. If your score is greater than or equal to ai, then you can increase your score by ai and remove ai from the array.

For each index i, output the maximum number of additional array elements that you can remove if you remove ai and then set your score to ai. Note that the removal of ai should not be counted in the answer.

Input

Each test contains multiple test cases. The first line contains an integer t (1t5000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1n105) — the length of the array.

The second line of each test case contains n integers a1,a2,,an (1ai109) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output

For each test case, output n integers, the i-th of which denotes the maximum number of additional array elements that you can remove if you remove ai from the array and then set your score to ai.

Example
Input
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
Output
4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4 
Note

In the first test case, the answers are as follows:

If we start with i=4, our initial score is a4=4 and a=[20,5,1,2]. We can remove 3 additional elements in the following order:

  1. Since 41, we can remove 1 and our score becomes 5. After this, a=[20,5,2].
  2. Since 55, we can remove 5 and our score becomes 10. After this, a=[20,2].
  3. Since 102, we can remove 2 and our score becomes 12. After this, a=[20].

If we start with i=1 we can remove all remaining elements in the array, so the answer is 4.

If we start with i=2, we can remove 3 additional elements in the following order: 1, 4, 2.

If we start with i=3, we can remove no additional elements.

If we start with i=5, we can remove 1 additional element: 1.