题目描述

期末考即将到来，上完最后一节数学课之后，大家就要开始准备期末考试了。

最后一节数学课下课前，小 $T$ 老师在黑板上写下了两个不同的数字（正整数） $X$ 和 $Y$ ，并给大家安排了一个课后作业，希望同学们能找到一个数字 $Z$，并且需要满足以下的两个要求：

$1.$ $Z$ 除以 $X$ 的余数与$Z$ 除以 $Y$ 的余数需要一致；

$2.$ $X$ 需要小于或等于 $Z$ 并且 $Y$需要小于或等于 $Z$。

请你来认真算一算，最小的 $Z$ 是多少？

输入格式

在第一行中输入一个正整数 $n$，表示一共有 $n$ 个不同的任务需要大家完成。

接下来的 $n$ 行中，第 $i$ 行有两个正整数 $X_i$和 $Y_i$，两个数字之间以一个空格间隔。

输出格式

输出 $n$ 行，每行输出一个整数表示当前任务的答案 $Z_i$。

输入样例1

1
4 6

输出样例1

12

输入样例2

2
997 999
1000 998

输出样例2

996003
499000

数据范围

对于 $30\%$ 的样例，有 $n \le 10 , 1 \le X, Y \le 10^3$。

对于 $100\%$ 的样例，有 $n \le 1000 , 1 \le X, Y \le 10^5$。