마법의 비트열

길이가 어떤 소수보다 정확히 $1$ 작은 비트열은 매직(magic) 일 수 있다. 예를 들어 1001은 그러한 문자열인데, 길이 $4$가 소수 $5$보다 $1$ 작기 때문이다.

어떤 비트열이 매직인지 확인하려면, 비트가 아닌 자리표시 기호 x를 문자열 끝에 하나 붙인 뒤 그 결과를 길이 $p$의 순환(cyclic) 문자열로 본다. 그런 다음 $p-1$개의 행으로 이루어진 정사각 비트 행렬을 만든다. $m$번째 행($1 \le m \le p-1$)은 순환 문자열의 매 $m$번째 비트를 $m$번째 비트부터 차례로 나열한 것이다. 즉, $m$번째 행의 $k$번째 원소는 순환 위치 $(k \cdot m) \bmod p$에 있는 비트이다.

문자열 1001($p = 5$)의 경우 행렬은 다음과 같다.

행렬의 행 수는 원래 비트열의 길이와 같다. 확장된 문자열의 길이 $p$가 소수이므로, 덧붙인 x는 결코 선택되지 않는다.

행렬의 모든 행이 원래 비트열이거나 그 비트 반전(complement)과 같으면, 그 비트열은 매직이다. 위 예에서는 모든 행이 1001 또는 그 반전 0110이므로 1001은 매직이다.

마지막 줄을 제외한 각 줄에는 소수 $p \le 100000$가 하나씩 주어진다. 마지막 줄에는 0이 하나 주어지며, 이 줄은 처리하지 않는다.

입력의 각 소수 $p$에 대해, 길이 $p-1$인 상수가 아닌(non-constant) 매직 비트열 중 사전순으로 가장 작은 것을 한 줄에 출력한다. 그러한 문자열이 없으면 Impossible을 출력한다.