#1610. 模立方根

模立方根

题目描述

这是一道模板题。

求关于 xx 的方程 x3a(modp)x^{3}\equiv a\pmod{p} 的解。

输入格式

第一行一个正整数 TT ,表示有 TT 组数据。

之后的 TT 行每行两个正整数 aapp

输出格式

每一组数据输出一行为方程的任意一个可行解,若无解则输出 0

样例

3
16 19
114 998244353
514 131071
0
504784271
0

数据范围与提示

pp 为奇素数, $T=10^{5},p<2^{30},a\in \mathbb{F}_{p}\setminus\{0\}$。