蛇蛇

題目敘述

蛇蛇最近剛學到 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

備註

Judge Setting