令 ，其中 都是整数，显然有 。令 表示 的最小公倍数，给定两个正整数 和 ,其中 是质数，并且保证 在模 意义下均不为 ,请计算 其在模 的值。
第一行包含一个正整数 ，表示有 组数据。
接下来是测试数据。每组测试数据只占一行，包含两个正整数 和 。
对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。
5 1 233 2 233 3 233 4 233 5 233
1 5 35 42 121
对于 的数据，，，，。 鸣谢 Tangjz 提供试题
