102. 蛇蛇

0 Judge

Code: 0


\( \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