在算法竞赛中，计算分数在模意义下的值十分常见。设质数 。给定 组数据，每组给出两个整数 ，请你计算下述表达式的值：

输入描述:

第一行输入一个整数 表示测试组数。 随后 行，每行输入两个整数 满足 ； 。

输出描述:

对每组数据，在一行上输出 的值（保证为 之间的整数）。