Description

青蛙有 $m+1$ 个无向图，编号为 $0\sim m$。每个图的点集都是 $V$，点集 $V$ 包含 $n$ 个点，编号为 $0\sim n-1$。起初所有的图都没有边存在。

接下来，在编号为 $x$ 的图中，对于所有在 $[0, n - 1]$ 中的编号 $i$，青蛙会将编号为 $i$ 的点与编号为 $(i\cdot x)\bmod n$ 的点连一条无向边。

他想知道这 $m+1$ 个图中有多少个图是连通的，这个问题交给你来回答。

注：

1. $\bmod$ 表示取模，$a\bmod b$ 表示 $a$ 除以 $b$ 得到的余数。
2. 在一张图中，若在点集内任意两个不同的点 $x, y$ 之间存在至少一条路径，则我们称这个图是连通的。

Input Format

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $n,m$，含义同上。

Output Format

共 $T$ 行，每行一个整数表示答案。

3
3 2
4 4
5 5

1
3
2

5
4 3
4 4
4 5
4 6
4 7

2
3
3
4
4

3
1145 1499
12344 123456
114514 1919810

2
41
17

Hint

【样例 #1 解释】

询问 1：

询问 2：

询问 3：

所以答案分别为 $1, 3, 2$。

【数据规模与约定】

本题开启捆绑测试。

• 对于 $100\%$ 的数据，保证 $1\le T\le 5,1\le n,m\le 10^{14}$。