Problem Description

有三个正整数 $a,b,c(0<a,b,c<10^6)$，其中 $c$ 不等于 $b$。若 $a$ 和 $c$ 的最大公约数为 $b$，现已知 $a$ 和 $b$，求满足条件的最小的 $c$。

Input

第一行输入一个 $n$，表示有 $n$ 组测试数据，接下来的 $n$ 行，每行输入两个正整数 $a,b$。

Output

输出对应的 $c$，每组测试数据占一行。

Samples

2
6 2
12 4

4
8