Description

这是一道模板题。

求关于 $x$ 的方程 $x^{3}\equiv a\pmod{p}$ 的解。

Input

第一行一个正整数 $T$ ，表示有 $T$ 组数据。

之后的 $T$ 行每行两个正整数 $a$、$p$。

Output

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

Samples

3
16 19
114 998244353
514 131071

0
504784271
0

Limitation

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