Description

给你正整数 $n$，和一个质数 $p$，你需要求出：

有 $T$ 组数据。

Input Format

第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个正整数 $n,p$，意义如题目描述。

Output Format

输出 $T$ 行，表示每组数据的答案。

4
16777216 998244353
72267859 998244353
2333333 19260817
1919810 2147481811

789885751
569626621
16351109
1416439247

Hint

数据范围：

对于 $10\%$ 的数据：$p = 998244353$
对于另外 $10\%$ 的数据：$p = 1004535809$
对于 $100\%$ 的数据：$1\le n < p \le 2^{31}-1$，$1 \le T \le 5$
保证 $p$ 为质数。

【提示】
请确保你的算法时间复杂度不高于 $\Theta(\sqrt n \log n)$，时限为 std 的十倍以上。