题目描述

有三只关系非常好的企鹅，她们的名字分别是 Anon、Tomori、Taki。

Anon 在和 Tomori 玩石子游戏，她们都极度聪明，Anon 和 Tomori 轮流操作，Anon 先手，初始时有 \(x\) 颗石子，每次操作必须恰好拿走 \(a\) 颗石子或者 \(b\) 颗石子，无法操作的企鹅将输掉这场游戏。

实际上，Taki 正在帮 Anon 和 Tomori 的石子游戏准备初始石子，Taki 喜欢 Tomori，想帮助 Tomori 获得胜利，因此她想知道至少需要多少颗石子（不能为 0）可以使得 Tomori 必定获得胜利？即已知 \(a, b\) 的情况下，最小化正整数 \(x\) 的值，使得第二位玩家必胜。

输入格式

第一行输入一个正整数 \(T(1 \le T \le 10^5)\) 表示数据组数：

每组数据第一行输入两个正整数 \(a, b(1 \le a, b \le 10^9)\)，表示每次操作的限制。

输出格式

对于每组数据，在一行中输出一个整数表示答案。

样例输入

1
1 2

样例输出

3