这是一个经典问题。现在给定数字 a，b，计算该结果 ax 1(modb)中x 的值数据保证 a 和b互质。
第一行输入一个正整数 q，表示查询的数量。 接下来 q行，每行输入两个正整数 a,b(中间用空格隔开)，表示一个查询。
输出q行，每行包含一个数字，表示对应查询的结果。
样例输入
2 38933863 27734475 14225530 70782091
样例输出
3881902 58213297