E. zxh的后宫管理系统

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

大家都认为 Sheauhaw 有一个庞大的后宫, 于是后宫管理系统应运而生. 该后宫管理系统为了满足 Sheauhaw 的特殊需求, 众生平等, 甚至可以录入任何实体的信息! 下面是该系统的运营方式:

后宫管理系统中一共存储了 个实体的信息, 每个实体都有一个从 的编号. 你可以向后宫管理员 Zeondik 查询某个实体的编号, 管理系统会返回一个编号 .

但是, 由于系统不稳定, 你暂时不能确定这个 的正确性, 假设真实编号是 . 好在你可以向 Sheauhaw 核实该返回值, 但是 Sheauhaw 比较神秘, 不会直接告诉你对或者错, 也不会直接告诉你编号, 而是用一种奇怪的方式核实: Sheauhaw 可以让你呈上一个整数 , 然后大发慈悲地告诉你 .

聪明无比的你一定有一个合适的 的选择, 将这个数字告诉 Sheauhaw 可以准确地判断 的正确性. 然而, Sheauhaw 喜欢小的东西, 管理员 Zeondik 要求你在所有合适的 中挑选一个最小的 告诉 Sheauhaw, 并检查你的 是否最小. 但 可能很大, 你只需要输出 取模的数值即可: 如果你的输出 , Zeondik 就会让你通过.

如果没有合适的 , 输出 .

输入格式

第一行一个整数 , 表示查询次数.

每组数据输入一行, 每行两个整数 , 表示编号范围和系统输出.

输出格式

每组输出输出一行, 一行一个整数, 表示 取模后的值. 如果没有合适的选择, 输出 .

样例

样例输入

3
10 1
10 4
10 7

样例输出

210
8
7

数据范围与提示