国际大学生小猪竞赛即将开始！本次竞赛设有不同的赛道，每个赛道对每支队伍的参赛人数都有具体要求。对于第 $k$ 个赛道，每支队伍的参赛人数必须恰好为 $k$。

Pigetown 大学有 $n$ 只小猪，它们希望以一种能使大学评分最大化的方式参赛。第 $i$ 只小猪的名字为 $s_i$，这是一个由小写英文字母组成的字符串。队伍的评分是其成员名字的最长公共前缀$^\dagger$的长度。大学的评分是该大学派出的所有队伍评分之和。每只小猪只能参加恰好一支队伍。

设 $f(i, j)$ 为当 Pigetown 大学仅派出前 $i$ 只小猪参加第 $j$ 个赛道（每支队伍恰好包含 $j$ 只小猪）时，大学能获得的最大评分。请对于每个 $1 \le i \le n$，计算 $\bigoplus_{j=1}^{i} (f(i, j) \times j)$，其中 $\oplus$ 表示按位异或运算。

$\dagger$：$m$ 个字符串 $t_1, t_2, \dots, t_m$ 的最长公共前缀的长度是最大的非负整数 $p$，满足 $p \le \min(|t_1|, |t_2|, \dots, |tm|)$ 且对于所有 $1 \le e \le p$ 以及 $1 \le i, j \le m$，都有 $t_{i,e} = t_{j,e}$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 5 \cdot 10^5$)。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)。

接下来的 $n$ 行中，第 $i$ 行包含一个字符串 $s_i$ ($1 \le |s_i| \le 10^6$)，表示第 $i$ 只小猪的名字。

保证字符串仅由小写英文字母组成。

保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^5$，且所有小猪名字的长度总和不超过 $10^6$。

输出格式

对于每组测试数据，在一行中输出 $n$ 个整数，以空格分隔。第 $i$ 个整数为 $\bigoplus_{j=1}^{i} (f(i, j) \times j)$。

样例

样例输入 1

2
5
aa
ab
ab
ac
d
1
aaaaa

样例输出 1

2 6 1 9 8
5