T228960 对称之美

周队是上下对称的。

在简单多边形中，对称轴是对称图形特有的一条直线。讲某个对称图形沿着它的对称轴折叠后，原本在对称轴两边的图形将会完全重合。 不过在本题中，我们所研究的却是与简单多边形无关的一个广义上对称图形：杨辉三角。杨辉三角具有对称性，其对称轴即为该三角的中轴线。把这条中轴线在杨辉三角中画出，容易发现，它会经过杨辉三角中奇数行最中间的元素，且会从偶数行的最中间两个数之间穿过。如果我们把杨辉三角的对称轴所经过的数写下来，可以排成一个下标从 $0$ 开始的无穷数列 $a_{0}=1,a_{1}=2,...$。 再给定一个质数 $p$ 和一个 $[1,p)$ 内的正整数 $m$，对于本题，你需要求出： $$\sum_{i=0}^{p-1}a_{i}\cdot m^{i} \pmod p$$

第一行有一个整数 $T$，表示数据组数。 对于每组数据，输入一行两个正整数 $p,m$。

对于每组数据，输出一行一个整数，为所求和式在模 $p$ 意义下的值。

对于 $40\%$ 的数据，$p\leq 10^{5}，T\leq 100$； 对于另外 $20\%$ 的数据，$m=1$； 对于 $100\%$ 的数据，$1\leq m\le p\leq 10^{14}，p$ 为质数，$1\leq T\leq 10^{4}$。 你可能会用到的数学公式： $$(a+b)^{n}=\sum_{i=0}^{n}\binom{n}{i}\cdot a^{i}\cdot b^{n-i}$$ 其中 $\binom{n}{m}$ 表示从 $n$ 个元素中无序地选取 $m$ 个元素的方案数，值为 $\frac{n!}{m!(n-m)!}$