#175. 模立方根

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: hly1204

题目描述

这是一道模板题。

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

输入格式

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

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

输出格式

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

样例

样例输入

3
16 19
114 998244353
514 131071

样例输出

0
504784271
0

数据范围与提示

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