题目背景

请注意本题非常规时空限制！

由于评测机性能差异，本题时限调整为2.5s

今天也是阳光明媚的午后呢！

克露丝卡尔酱趴在桌上，盯着这道题目发呆。

“呜呜……又是二进制串……又是循环同构……”

旁边的同学探过头来：“克露丝卡尔酱还在和这道题苦战吗？”

“才、才不是在苦战呢！只是在思考人生啦！”

克露丝卡尔酱嘟着嘴，手中的笔无意识地转着圈。

不过既然都拿起来了，那就试着解解看吧！

题目描述

长度为 $n$ 的二进制串 $S$ 初始时所有比特均为零，给定 $n$ 次操作，每次操作先翻转 $S$ 的一个比特，再输出满足以下两个条件的二进制串二元组 $(A,B)$ 的个数：

• $A,B$ 均与 $S$ 循环同构。
• $A$ 的每个前缀的汉明权重都不小于相同长度的 $B$ 的前缀的汉明权重。

称两个字符串循环同构，当且仅当其中一个字符串能够通过若干次左旋操作变为另一个字符串。这里的“左旋”指的是：把字符串的首个字符移动到末尾。例如：$\texttt{abc}$ 经过一次左旋操作得到 $\texttt{bca}$ ，因此它们循环同构，但它们不与 $\texttt{cba}$ 循环同构。

二进制串的汉明权重定义为其中 $\texttt{1}$ 的数量。

输入格式

本题有多组测试数据。

首先输入一行，包含一个整数 $T$ ($1\le T\le 2000$)，表示测试数据组数。

每组数据首先输入一行，包含一个整数，表示二进制串长度 $n$ ($1\le n\le 2000$)。

之后输入一行，包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 次操作所翻转的比特的下标，下标从 $1$ 开始。

保证 $\sum n\le 2000$。

输出格式

输出 $T$ 行，每行 $n$ 个整数，表示每次翻转后满足条件的二元组个数。

2
5
1 2 3 4 1
3
2 1 1

15 13 13 15 13
6 6 6

提示

在第二组样例中，进行第二次操作后，$S$ 变为 $\texttt{110}$，此时满足条件的 $(A,B)$ 共有 $6$ 个，分别为：

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