Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a sequence of integers $A_{1}, A_{2}, \ldots, A_{N}$. He takes a sheet of paper and for each non-empty subsequence $B$ of this sequence, he does the following:
1. For each integer which appears in $B$, count its number of occurrences in the sequence $B$.
2. Choose the integer with the largest number of occurrences. If there are several options, choose the smallest one.
3. Finally, write down the chosen integer (an element of $B$) on the sheet of paper.

For each integer between $1$ and $N$ inclusive, find out how many times it appears on Chef's sheet of paper. Since these numbers may be very large, compute them modulo $1,000,000,007$ ($10^{9} + 7$).

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output ------
For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should be the number of occurrences of $i$ on Chef's sheet of paper.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ A_{i} ≤ N$ for each valid $i$
the sum of $N$ over all test cases does not exceed $500,000$

------ Subtasks ------
Subtask #1 (20 points): the sum of $N$ over all test cases does not exceed $5,000$

Subtask #2 (10 points): $A_{1}, A_{2}, \ldots, A_{N}$ is a permutation of the integers $1$ through $N$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------
3

3

2 2 3

2

1 2

3

1 2 2
----- Sample Output 1 ------
0 6 1

2 1

3 4 0
----- explanation 1 ------
Example case 3: There are $7$ non-empty subsequences:
- $[1]$ (Chef writes down $1$)
- $[2]$ (Chef writes down $2$)
- $[2]$ (Chef writes down $2$)
- $[1, 2]$ (Chef writes down $1$)
- $[1, 2]$ (Chef writes down $1$)
- $[2, 2]$ (Chef writes down $2$)
- $[1, 2, 2]$ (Chef writes down $2$)

见题面

见题面