곱셈

비 오는 어느 토요일, 스타시(Staś)는 밖에 나가 공놀이를 할 수 없어 집에 머물며 자신이 가장 좋아하는 일, 곱셈을 하며 시간을 보냈다.

스타시는 $1$ 에서 시작해, 떠오르는 대로 자릿수가 최대 5자리인 자연수들을 차례로 곱해 나갔다. 그렇게 얻은 수에 마지막으로 $1$ 을 더했더니, 그 수 $p$ 가 소수였다.

이를 좋은 징조로 여긴 스타시는 놀이를 이어갔다. 이번에는 서로 다른 두 자연수 $a$, $b$ 를 골랐다. 역시 $1$ 에서 시작했지만, 이번에는 결과를 $p$ 로 나눈 나머지가 $b$ 가 될 때까지 매번 같은 수 $a$ 를 곱했다. 마침내 성공하자 스타시는 곱셈에 지쳐 잠들었다.

스타시는 이 두 번째 놀이에서 곱셈을 몇 번 해야 했을까?

첫째 줄에 테스트 집합의 개수 $Z$ 가 주어진다 ($1 \le Z \le 2$).

둘째 줄에는 위에서 설명한 방식으로 스타시가 얻은 소수 $p$ 가 주어진다 ($2 \le p \le 10^{18}$). $p - 1$ 은 자릿수가 최대 5자리인 자연수들의 곱이므로, $p - 1$ 의 모든 소인수는 $99999$ 이하이다.

이어지는 $Z$ 개의 줄에는 각 줄마다 서로 다른 두 자연수 $a$, $b$ 가 주어진다 ($1 < a, b < p$).

각 테스트 집합에 대해, $1$ 에서 시작해 $a$ 를 곱해 나갈 때 나머지가 $b$ 가 되기까지 필요한 곱셈 횟수를 한 줄에 하나씩 출력한다. 이는 $a^k \equiv b \pmod{p}$ 를 만족하는 가장 작은 양의 정수 $k$ 이다. $b$ 를 얻는 것이 불가능하면 $-1$ 을 출력한다.

위 예시에서 소수 $p = 13$ 은 다음과 같이 만들어졌다. 스타시는 먼저 $4$ 를 곱했는데(즉 $4$ 에서 시작), $4$ 는 소수가 아니다. 이어서 $3$ 을 곱해 $12$ 를 얻었고, 마지막으로 $1$ 을 더해 소수 $13$ 을 얻었다.

$1$ 에서 시작해 $12$ 를 계속 곱하면 $12, 1, 12, 1, \dots$ 가 반복되어 $9$ 는 결코 나오지 않는다. 반면 $4$ 를 계속 곱하면 $4, 3, 12, 9, 10$ 이 차례로 나오므로, $10$ 은 다섯 번의 곱셈 만에 얻어진다.