商店里有无限种物品，对于任意正整数 ，都存在一种重量为 、价格为 的物品。每种物品的数量无限。 你最多可以购买 个物品，希望得到总重量恰好为 。请计算：在满足总重量等于 的前提下，所需的最低总价格是多少？将结果对 取模后输出。

输入描述:

每个测试文件包含多组测试数据。第一行输入一个整数 表示测试组数。接下来每组数据描述如下： 每行包含两个整数 。

输出描述:

对于每组测试数据，输出一行一个整数，表示最低总价格对 取模后的结果。