9116: Semi-Puzzle: Brain Storm

Given two positive integers $a,m$. Find a non-negative integer $u$, where au≡u(modm)a^{u} \equiv u \pmod{m}au≡u(modm).

There are multiple test cases.
The first line contains one integer $T$ (1≤T≤10001\le T \le 10001≤T≤1000), representing the number of test cases.
Each of the following $T$ lines contains two integers $a,m$ (1≤a<m≤1091\le a < m \le 10^91≤a<m≤109).

For each test case, output a line containing a single integer $u$ (0≤u≤10180 \le u \le 10^{18}0≤u≤1018), representing the answer. It is guaranteed that the answer exists.

5
1 2
2 3
6 7
12 15
114514 1919810

3
10
36
96
104419494656