멀티버스를 여행하는 한별이를 위한 안내서

멀티버스 여행을 하다 공간이동 스킬을 잃어버린 한별이는 어느새 은하의 수중에 공간이동 스킬이 있는 것을 발견했다! 한별이는 공간이동 스킬을 돌려받기 위해 은하와 아래와 같은 내기를 하기로 했다.

은하만 알고 있는 $1$ 이상 $10^8$ 미만의 두 정수 $N$, $K$가 준비되어 있다. 한별이는 은하에게 아래와 같은 질문을 최대 $Q$번 할 수 있다.

• ? $x$ $y$: $N\times K^x \equiv N\times K^y \pmod{10^8}$인가?

한별이는 $N\times K^a \equiv N\times K^b \pmod{10^8}$를 만족하는 두 개의 서로 다른 음이 아닌 정수 $a$, $b$ 중에서, $a$를 최소화하는 가장 작은 $b$의 값을 구해야 한다. 은하는 공정한 내기를 위해 항상 그러한 $b$가 존재하도록 $N$, $K$를 선택한다. 한별이는 이 내기에서 이길 수 있게끔 당신에게 프로그램을 작성해 줄 것을 부탁했다.

• $1\leq T\leq 100$

당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.

• C — fflush(stdout)
• C++ — std::cout.flush()
• Python — sys.stdout.flush()
• Java — System.out.flush()
• 그 외의 언어는 각 언어의 Documentation을 참고한다.

또한, 예제의 빈 줄은 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 추가된 것이며, 실제 입출력에는 빈 줄이 나타나지 않는다.