给定正整数对 ，求乘法逆元 。

输入描述:

第一行输入测试组数 。接下来 行，每行输入两个整数 。需要特别注意的是，数据不保证 为质数！

输出描述:

对于每组测试用例，输出一行一个正整数，表示表达式  的值。