\(
\newcommand{\ord}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\opord}{\operatorname{\mathcal{O}}}
\newcommand{\argmax}{\operatorname{arg\,max}}
\newcommand{\str}[1]{\texttt{"#1"}}
\)
蛇蛇
題目敘述
蛇蛇最近剛學到 Treap,他需要一些亂數來實作 Treap,但他又不喜歡函式庫裡面的亂數產生器,因此他要自己生成亂數。他生成亂數的方法是每次挑兩個數字 $a$ 跟 $N$,產生出來的亂數序列就是 $a^1\pmod{N}$, $a^2\pmod{N}$, $a^3\pmod{N}$, ...,但是這個序列很快就會有重複的數字產生。
蛇蛇很好奇第一個重複的數字是什麼,你可以幫幫他嗎?
輸入說明
第一行會有一個數字 $T$ 代表有 $T$ 筆測試資料。
接下來會有 $T$ 行,每一行會包含兩個數字 $a$, $N$ 代表一開始的數字以及取模數。
其中 $0\leq a \le N \leq 10^{16}$
輸出說明
對於每一筆測試資料,請輸出一個第一個重複的數字是多少。
範例輸入
3
3 6
2 4
2 3
範例輸出
3
0
2
配分方法
- 10% $1 \leq T \leq 10$, $1 \leq N \leq 100$
- 40% $1 \leq T \leq 10^3$, $1 \leq N \leq 10^5$
- 60% $1 \leq T \leq 10^5$, $1 \leq N \leq 10^9$
- 100% $1 \leq T \leq 10^6$, $1 \leq N \leq 10^{16}$
Hints
蛇蛇最喜歡 Treeeeeeeeeeeeeeeeeeeeeeeeap 了!
備註
Judge Setting
run-time limit: 1500 ms
memory limit: 65536000 byte
測資數量: 0