Please note the unconventional time and memory limits for this problem!

A binary string $S$ of length $n$ is initially all zeros. You are given $n$ operations. In each operation, you first flip one bit of $S$, then output the number of pairs of binary strings $(A, B)$ that satisfy the following two conditions:

• Both $A$ and $B$ are cyclically isomorphic to $S$.
• The Hamming weight of every prefix of $A$ is no less than the Hamming weight of the prefix of $B$ of the same length.

Two strings are said to be cyclically isomorphic if and only if one can be transformed into the other through a number of left cyclic shifts. A "left cyclic shift" means moving the first character of the string to the end. For example, $abc$ becomes $bca$ after one left cyclic shift; thus, they are cyclically isomorphic, but they are not cyclically isomorphic to $cba$.

The Hamming weight of a binary string is defined as the number of $1$s it contains.

Input

The input contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 2000$), representing the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 2000$), representing the length of the binary string.

The next line contains $n$ integers, where the $i$-th integer represents the index of the bit flipped in the $i$-th operation (1-indexed).

It is guaranteed that $\sum n \le 2000$.

Output

Output $T$ lines, each containing $n$ integers, representing the number of pairs satisfying the conditions after each flip.

Examples

Input 1

2
5
1 2 3 4 1
3
2 1 1

Output 1

15 13 13 15 13
6 6 6

Note

In the second example, after the second operation, $S$ becomes $110$. There are 6 pairs $(A, B)$ that satisfy the conditions:

• $A = 110, B \in \{110, 101, 011\}$
• $A = 101, B \in \{101, 011\}$
• $A = B = 011$