캬루

프린세스 커넥트! Re:Dive 8장 "엇갈리는 마음", 15화 "절대로 양보할 수 없는 것" 내용 일부 발췌

이번에 캬루는 소수를 배신했다. 소수의 한 자리를 바꾸어서 소수가 아니게 만들어버렸다. 구체적으로는, $0$으로 시작하지 않는 $N$자리 소수 $P$에 대해 어떤 수 $Q$가 $P$-캬루라는 것은 다음을 모두 만족하는 것을 의미한다.

• $Q$는 $2$ 이상의 $N$자리 정수이며, $0$으로 시작하지 않는다.
• $P$와 $Q$의 서로 다른 자릿수는 하나뿐이다.
• $Q$는 소수가 아니다.

다음은 $N=2, P=19$일 때 $P$-캬루와 $P$-캬루가 아닌 수의 예시이다.

• $Q = 9$는 $1$자리 정수이므로 $19$-캬루가 아니다. $09$처럼 수가 $0$으로 시작할 수는 없다.
• $Q = 92$는 $P=19$와 서로 다른 자릿수가 두 개이므로 $19$-캬루가 아니다.
• $Q = 29$는 소수이기 때문에 $19$-캬루가 아니다.
• $Q = 16, 49$ 등은 $19$-캬루이다.

$N$자리 소수 $P$가 주어졌을 때, $P$-캬루인 수가 적어도 $N$개 있다는 것을 증명할 수 있다. 이 $N$개의 수를 직접 찾아보자.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. $(1 \le T \le 3\,545)$

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에는 문제의 $N$과 $P$가 공백으로 구분되어 주어진다. $(1 \le N \le 100;$ $10^{N-1} \le P \lt 10^N;$ $P$는 소수$)$

주어지는 모든 $N$의 합은 $3\,545$ 이하이다.

각 테스트 케이스마다 $N$개의 줄을 출력한다.

$i$번째 줄에는 $Q_i$와 $R_i$를 공백으로 구분하여 출력한다. $Q_i$는 서로 다른 $P$-캬루들이며, $R_i$는 $2 \le R_i < Q_i$인 $Q_i$의 약수이다.