You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解，若无解，输出"-1"。

输入格式

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

接下来T行，每行两个正整数a,b(2≤a,b≤2×${10}^9$) 。

输出格式

对于每组数据，输出同余方程的最小正整数解，若无解，输出"-1"（没有引号）。

2
3 10
2 4

7
-1