本题没有可用的提交语言。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

众所周知，杰神和龟神都是 $OP$。

出于整活的 Ocean，决定整一个小游戏，来让龟神有必胜的策略：

1. 两个玩家共用一个账号，账号一开始有 $n$ 个原石；
2. 规定杰神先手，龟神后手；
3. 每一轮，两个玩家可以选择消耗 $a$ 个原石 或者 $b$ 个原石进行抽卡；
4. 如果原石不够，那么玩家必须要氪金，但很显然，双方都是不乐意氪金的，因而我们判定这个玩家输了。

这是一个假想的游戏，因而我们假设这个游戏账号一开始拥有无穷多的原石。

在游戏开始前，Ocean 可以偷偷消耗一定数量的原石，来让游戏开始时的原石总数等于 $n$。

有趣的是，如果 $n$ 取一些特定的值，杰神是一定输的，因为聪明的龟神可以观察杰神的决策，然后让自己尽可能不输。

虽然，在游戏刚开始前，这个小技俩就被聪明的杰神识破了，但 Ocean 还是想知道，$n$ 为多少时，龟神必胜，并希望你能告诉他。

输入格式

本题有多组数据。

第一行为数据的总数 $t$。

从第二行开始，每一行包含两个整数，为本组数据下，每一轮每个玩家可以消耗的原石数 $a, b$。

输出格式

对于每一组数据，输出一个整数 $n\ (1 \leq n \leq 10 ^ 6)$，使龟神必胜。

如果有多个解，输出任意一个即可。

可以证明一定有解。

样例

样例输入1

3
1 4
1 5
9 26

样例输出1

2
6
3

说明

$1 \leq t \leq 100$

$1 \leq a < b \leq 100$