放学后，你只花了 10 分钟就完成了所有作业。虽然大多数课程都很简单且枯燥，但你依然期待着明天的课。因为你喜欢和 Nozomi 一起玩游戏。也许你已经爱上她了？

为了让明天的课变得更有趣，你正在研究一个名为“骑士花园”（Knight Garden）的酷炫游戏，并想在明天和她分享这个游戏。

游戏在一个 $n \times m$ 的棋盘上进行。有一个 $(r, s)$-骑士从左上角出发。在每一步移动中，如果目标位置在棋盘内，该骑士可以从 $(x, y)$ 跳到 $(x \pm r, y \pm s)$ 或 $(x \pm s, y \pm r)$。例如，如果一个 $(1, 2)$-骑士位于 $5 \times 5$ 棋盘的 $(3, 3)$ 位置，则该骑士有八种可能的移动方式。

我们称一个在 $n \times m$ 棋盘上的 $(r, s)$-骑士是幸运的，如果它可以访问棋盘上的所有位置。注意，每个位置可以被多次访问。你认为仅仅让 Nozomi 判断一个骑士是否幸运太简单了。因此，你想知道当给定 $n, m$ 时，有多少个整数对 $(r, s)$ 满足 $1 \le r \le s \le \max(n, m)$ 且 $(r, s)$-骑士在 $n \times m$ 的棋盘上是幸运的？和往常一样，有 $T$ 个类似的询问。

输入格式

第一行包含一个整数 $T$。

接下来的 $T$ 行，每行包含两个整数 $n, m$。

数据范围

• $1 \le T \le 5000$
• $1 \le n, m \le 10^7$

输出格式

对于每个询问，输出该棋盘上幸运骑士的数量。

样例

输入 1

4
4 4
4 8
8 8
100 100

输出 1

1
1
4
518