Background

Please note that this problem has non-standard time and memory limits!

Due to performance differences among judge machines, the time limit has been adjusted to 2.5 s.

It is another sunny afternoon!

Kruskal-chan lies on the desk, staring at this problem in a daze.

“Wuwu... binary strings again... cyclic isomorphism again...”

A classmate leans over: “Kruskal-chan is still struggling with this problem?”

“I-I’m not struggling at all! I’m just thinking about life!”

Kruskal-chan pouts, and the pen in her hand spins in circles unconsciously.

But since you have already picked it up, let’s try to solve it!

Problem Description

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

• Both $A$ and $B$ are cyclically isomorphic to $S$.
• For every prefix of $A$, its Hamming weight is not less than the Hamming weight of the prefix of $B$ of the same length.

Two strings are called cyclically isomorphic if and only if one of them can be transformed into the other by performing several left-rotation operations. Here, a “left rotation” means moving the first character of the string to the end. For example, $\texttt{abc}$ becomes $\texttt{bca}$ after one left rotation, so they are cyclically isomorphic, but they are not cyclically isomorphic to $\texttt{cba}$.

The Hamming weight of a binary string is defined as the number of $\texttt{1}$s in it.

Input Format

This problem contains multiple test cases.

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

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

The next line contains $n$ integers, where the $i$-th integer denotes the index of the bit flipped in the $i$-th operation. Indices start from $1$.

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

Output Format

Output $T$ lines. Each line contains $n$ integers, representing the number of valid ordered pairs after each flip.

2
5
1 2 3 4 1
3
2 1 1

15 13 13 15 13
6 6 6

Hint

In the second sample, after the second operation, $S$ becomes $\texttt{110}$. At this time, there are $6$ valid pairs $(A, B)$, which are:

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

Translated by ChatGPT 5