字典树（Trie）是像字典一样的树。如下图所示，字典树用边来代表字符，每个节点到它的所有子节点的边上的字符互不相同，而从根节点到树上某一节点的路径就代表一个字符串，例如 $1→4→8→12$ 表示字符串 “caa”。

注意，本题中字符集为所有正整数，并非 $26$ 个小写字母。

有 $n$ 个非空的字符串 $S_1,S_2,\dots ,S_n$ 被构造成了一棵字典树 $T$，它包含 $m$ 个节点，其中 $1$ 号节点为根节点，剩下节点的编号被打乱了。现在给定 $T$，请还原这 $n$ 个非空的字符串。

若有多个可行方案，请输出 $n$ 最小的方案；若在此基础上还有多个可行方案，请输出 $[S_1,S_2,\dots ,S_n]$ 字典序最小的方案。

字符串序列 $[A_1,A_2,\dots ,A_n]$ 的字典序小于字符串序列 $[B_1,B_2,\dots ,B_n]$ 当且仅当存在某个 $k$ $(1\leq k\leq n)$ 满足字符串 $A_i=B_i(1\leq i<k)$ 且字符串 $A_k<B_k$。请注意，这里的字符串比较也为字典序比较。

字符串 $C$ 的字典序小于字符串 $D$ 当且仅当 $C$ 是 $D$ 的前缀或者存在某个 $k$ $(1\leq k\leq \min(|C|,|D|))$ 满足 $C[i]=D[i](1\leq i<k)$ 且 $C[k]<D[k]$，其中 $C[k]$ 表示字符串 $C$ 的第 $k$ 个字符。

输入格式

第一行包含一个正整数 $T$ $(1\leq T\leq 500)$，表示测试数据的组数。

每组数据第一行包含一个正整数 $m$ $(2\leq m\leq 200,000)$，表示字典树的节点数。

第二行包含 $m−1$ 个正整数 $f_2,f_3,\dots ,f_m$ $(1\leq f_i<i)$，依次表示每个节点的父节点编号。

输入数据保证 $\sum m\leq 2,000,000$。

输出格式

每组数据第一行输出一个正整数 $n$，表示字符串的数量。

接下来 $n$ 行，第 $i$ 行的输出代表字符串 $S_i$。由于字符串可能很长，请输出它的哈希值

$$\left(\sum_{j=1}^{|S_i|} 998,244,353^{|S_i|-j}\cdot S_i[j]\right)\bmod 2^{64} $$

样例

输入

4
2
1
3
1 1
4
1 2 1
6
1 2 1 4 5

输出

1
1996488707
2
998244354
1992983577591021572

提示

样例一的方案为：$S_1=[1]$。

样例二的方案为：$S_1=[1], S_2=[2]$。

样例三的方案为：$S_1=[1], S_2=[2,1]$。

样例四的方案为：$S_1=[1,1], S_2=[2,1,1]$。