### 问题描述 这是一个经典问题。现在给定数字 $a$，$b$，计算该结果 $ax \equiv 1 \left(\bmod b\right)$ 中 $x$ 的值。 数据保证 $a$ 和 $b$ 互质。 ### 输入格式 第一行输入一个正整数 $q$，表示查询的数量。 接下来 $q$ 行，每行输入两个正整数 $a,b$ (中间用空格隔开)，表示一个查询。 ### 输出格式 输出 $q$ 行，每行包含一个数字，表示对应查询的结果。 ### 样例输入 ```text 2 38933863 27734475 14225530 70782091 ``` ### 样例输出 ```text 3881902 58213297 ``` ### 评测数据规模 $2\leq q\leq 10^2,1\leq n \leq 10^{9}$。