Statement is not available in English language
H. Árvore de Strings
time limit per test
1.2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Música - Reason

Gon está prestes a subir a Árvore do Mundo, uma árvore com mais de 1700m de altura. Como Gon adora árvores e vai passar bastante tempo escalando, ele decidiu resolver a seguinte questão sobre uma outra árvore mágica:

Considere uma árvore enraizada no vértice 1 com uma letra escrita em cada aresta. Considere agora para todo par de vértices u e v em que u é ancestral direto ou indireto de v. O caminho de u para v pode ser representado por uma série de k arestas e1, e2, ..., ek. Seja cei o caractere escrito na aresta ei. Definimos s(u, v) como a string formada pelas arestas ei na ordem que aparecem: s(u, v) = ce1 + ce2 + ... + cek, em que  +  representa a concatenação dos caracteres.

Para cada nó u imprima o tamanho da maior string lexicograficamente que começa em u. Ou seja, entre todos os v tal que u é ancestral de v, seja s(u, v * ) a maior string lexicograficamente. Imprima |s(u, v * )|.

Também imprima na linha seguinte a maior string lexicograficamente entre todas as possíveis. Ou seja, maxu ancestral de v(s(u, v)).

Input

A primeira linha contém um inteiro t ≤ 2·105, representando a quantidade de casos de teste. Cada caso de teste segue no seguinte formato:

Na primeira linha leia o tamanho da árvore n, 1 ≤ n ≤ 2·105. Por fim, seguem n - 1 linhas com um inteiro pi e um caracter ci, representando uma aresta direcionada de pi para i + 1, com 1 ≤ i < n. É garantido que para todo i, pi < i + 1 e que ci é uma letra latina minúscula (de "a" até "z").

Também é garantido que a soma de n nos casos de teste é no máximo 2·105.

Output

Para cada um dos casos de teste imprima primeiro uma linha com n caracteres, representando o tamanho da maior string que começa no nó i, para 1 ≤ i ≤ n, nessa ordem. Na linha seguinte imprima a maior string lexicograficamente que pode ser obtida, entre todos os pares de vértices u e v, em que u é ancestral de v.

Examples
Input
2
5
1 b
1 a
3 b
4 a
5
1 a
2 b
3 a
3 a
Output
1 0 2 1 0
ba
3 2 1 0 0
ba
Input
3
5
1 a
1 d
2 a
4 b
5
1 c
2 d
1 c
3 c
5
1 c
1 d
3 a
4 b
Output
1 2 0 1 0
d
3 2 1 0 0
dc
3 0 2 1 0
dab