到底是互质还是整除？
有 组询问，每次给定 ，求：
由于答案会很大，你只需要输出答案对 取模的结果。
上式中：
第一行一个正整数 ，表示有 组询问。
接下来 行，每行两个正整数 ，表示一次询问。
行，每行一个非负整数表示答案。
6 2 2 3 3 4 4 5 5 6 6 7 7
14 130 566 2310 4778 13934
2 114 514 2333 23333
603971168 547492264
对于 的数据：保证
对于 的数据：保证 。
来源：洛谷
这题已经弱化的不能再弱化了，如果样例都过不了，再过几年再来挑战这道题吧！