소수 판정과 소인수분해

다음 $Q$개의 질의를 순서대로 처리해 보자.

• $0\ N$: $N$이 소수인지 판별한다.
• $1\ N$: $N$을 소인수분해한다.
• $2\ A\ B\ M$: $AB\bmod M$을 구한다.
• $3\ A\ B\ M$: $A^B\bmod M$을 구한다.

$0^0=1$로 정의한다.

첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 2\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 질의가 다음 형식 중 하나로 주어진다. 각 질의의 정수는 공백으로 구분되어 주어진다.

• $0\ N$: 정수 $N$이 주어진다. $(-10^{18} \le N \le 10^{18})$
• $1\ N$: 정수 $N$이 주어진다. $(1 \le N \le 2^{63}-1)$ 이 질의는 최대 $20$개 주어진다.
• $2\ A\ B\ M$ 또는 $3\ A\ B\ M$: 세 정수 $A$, $B$, $M$이 공백으로 구분되어 주어진다. $(0 \le A, B \le 10^{18}; 1 \le M \le 10^{18})$

각 질의의 답을 질의가 주어진 순서대로 한 줄에 하나씩 출력한다.

소수 판정은 소수이면 $1$을, 그렇지 않다면 $0$을 출력한다. 소인수분해는 서로 다른 소인수의 수 $K$를 먼저 출력하고, 각 소인수와 지수를 소인수의 오름차순으로 출력한다. $N=1$이면 $K=0$이다. 한 줄의 값은 공백으로 구분하여 출력한다.

나머지 두 종류의 질의는 계산한 나머지를 출력한다.