주기성

비토티아의 왕 바이테아사르는 신하들의 이름을 개혁하기로 했다. 비토티아 사람들의 이름에는 반복되는 조각이 자주 들어 있다. 예를 들어 이름 Abiabuabiab에는 조각 abiab가 두 번 나타난다. 바이테아사르는 각 신하의 이름을 원래 이름과 길이가 같은 비트열로 바꾸려 하며, 새 이름이 원래 이름의 반복 구조를 그대로 반영하기를 바란다.

편의상 대문자와 소문자는 같은 것으로 본다. 문자열 또는 비트열 $w = w_1 w_2 \dots w_k$ 에 대해, $1 \le p < k$ 인 정수 $p$가 모든 $i = 1, \dots, k - p$ 에 대해 $w_i = w_{i+p}$ 를 만족하면 $p$를 $w$의 주기라고 한다. $w$의 모든 주기를 모은 집합을 $\mathrm{Per}(w)$ 로 나타낸다. 예를 들어 $\mathrm{Per}(\text{ABIABUABIAB}) = \{6, 9\}$, $\mathrm{Per}(01001010010) = \{5, 8, 10\}$, $\mathrm{Per}(0000) = \{1, 2, 3\}$ 이다.

바이테아사르는 모든 이름을 다음 조건을 만족하는 비트열로 바꾸기로 했다.

• 원래 이름과 길이가 같다.
• 원래 이름과 주기의 집합이 정확히 같다.
• 위 두 조건을 만족하는 비트열 중 사전순으로 가장 작다.

예를 들어 ABIABUABIAB는 01001101001로, BABBAB는 010010으로, BABURBAB는 01000010으로 바뀐다.

신하들의 현재 이름을 새로운 비트열 이름으로 바꾸는 프로그램을 작성하라.

첫 번째 줄에 바꿀 이름의 개수 $k$ 가 주어진다 ($1 \le k \le 20$). 이어지는 $k$ 개의 줄에 이름이 한 줄에 하나씩 주어진다. 각 이름은 영어 대문자로만 이루어지며, 길이는 최소 $1$, 최대 $200\,000$ 이다.

전체 배점의 30%에 해당하는 데이터에서는 모든 이름의 길이가 $20$ 이하이다.

$k$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 입력 이름에 대응하는 비트열(0과 1로만 이루어지며 사이에 구분자가 없는 문자열)을 출력한다. 어떤 이름에 대해 적절한 비트열이 존재하지 않으면 그 줄에는 대신 XXX(따옴표 제외)를 출력한다.

비트열 $x_1 x_2 \dots x_k$ 가 비트열 $y_1 y_2 \dots y_k$ 보다 사전순으로 작다는 것은, 어떤 인덱스 $i$ ($1 \le i \le k$) 가 존재하여 $x_i < y_i$ 이고 모든 $j = 1, \dots, i - 1$ 에 대해 $x_j = y_j$ 인 경우를 뜻한다.