【模板】逆元

题号：NC226824
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

求x模p意义下的逆元，若不存在，请输出-1.

逆元的定义：

x模p意义下的逆元，指的是求y，使得 $x*y ≡1 \space mod \space p$ 。

第一行一个整数T，表示T个测试用例。(1 <= T <= 10000)
接下来T行，每行2个整数x, p（2 <= x < p <= 10^9）

输出每组测试用例的答案

示例1

复制

2
4 8
2 1000000007

复制

-1
500000004

2*500000004 = 1000000008

1000000008 在模1000000007意义下与1同余。