Problem B
Miller-Rabin

Ákvarðið hvort heiltala $a$ er Miller-Rabin vitni fyrir heiltölu $n$.

Inntak

Fyrsta línan inniheldur fjölda tilrauna $1 \leq t \leq 10^5$. Hver tilraun samanstendur af tveimur línum: Fyrsta línan inniheldur heiltölu $3 \leq n \leq 2^{63}-1$. Seinni línan inniheldur heiltölu $1 \leq a \leq \min \{ n - 1, 2^{31}-1\} $.

Úttak

Skrifið línu fyrir hverja tilraun, með $1$ ef $a$ er Miller-Rabin vitni fyrir $n$, eða $0$ ef ekki.

2
561
2
172947527
17

1
0