### 问题描述 小蓝和小桥在学校里上美术课，老师正在教他们画正多边形。 小蓝突发奇想，给每个正多边形的边涂上了不同的颜色，并保证正多边形每条边的颜色互不相同。 小桥看见了，非常好奇，如果给 $n$ 个完全相同的正 $m$ 边形的每条边涂上颜色，并且任意两个正 $m$ 边形经过旋转也不会重合，至少需要多少种不同的颜料呢？ 重合指的是两个正 $m$ 边形在二维平面上重叠，对应重合的 $m$ 条边中至少有一条颜色不一致。 ### 输入格式 第一行输入一个正整数 $t$，表示测试用例组数。$(1\le t\le 10)$ 对于每组测试数据： 输入一行，为 $2$ 个正整数 $n,m$。$(1\leq n \leq 10^9,3\le m\le 10^9)$ ### 输出格式 对于每组测试数据： 输出一行，为至少需要的不同颜色数。 ### 样例输入 ``` 2 2 4 3333 7 ``` ### 样例输出 ``` 4 8 ``` ### 说明 对于测试样例 $1$：  对于样例，我们最少只需要四种颜色即可保证两个正四边形任意旋转不完全重合。