극비 메시지

요원 존은 극비 수 $N$을 알고 있다. 그는 $N$의 각 자리를 밑이 $b$인 진법으로 적은 뒤, 고대 바이토테인 언어의 단어로 바꿔 썼다. 각 자리는 영어 소문자 나열로 표현된다. 그는 메시지의 맨 앞, 맨 뒤, 또는 연속한 두 자리 사이에 임의의 문자를 0개 이상 넣었다. 임의의 문자는 자리 단어 안에 나타나지 않는다. 바이토테인에는 0을 가리키는 단어가 없었고, $N$에는 0인 자리가 없다. 암호화된 메시지는 모호할 수 있다. 주어진 메시지를 만들 수 있는 가장 큰 수 $N$을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 밑 $b$ ($3 \le b \le 5 \cdot 10^4$)로 시작한다. 이어서 $b-1$개의 줄이 주어지며, $i$번째 줄에는 자리 $i$의 단어가 주어진다. 단어는 비어 있지 않고 서로 다르며, 단어 길이의 합은 $5 \cdot 10^5$ 이하이다. 각 테스트 케이스의 마지막 줄은 암호화된 메시지이며, 길이는 $3 \cdot 10^5$ 이하이다.

각 테스트 케이스마다 조건을 만족하는 가장 큰 수의 자리를 공백으로 구분해 한 줄에 출력한다. 조건을 만족하는 수가 없으면 0을 출력한다.