青蛙有 $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
**本题有多组数据**。
第一行一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个整数 $n,m$，含义同上。
## Output
共 $T$ 行，每行一个整数表示答案。
[samples]
## Background
小青蛙被关进了监狱的小黑屋里，他遭受了接连不断的折磨，无论是肉体上还是精神上。
他的精神萎靡不振，他的身体行动迟缓。
有些东西被暂时的压制了，但这些东西越是被压制，它反弹时威力就越大。
他需要一个契机。
## Note
**【样例 #1 解释】**
询问 1：
| 图的编号 | 边集 | 图是否连通 |
| :------: | :-----------------: | :--------: |
| $0$ | $(0,0),(1,0),(2,0)$ | 是 |
| $1$ | $(0,0),(1,1),(2,2)$ | 否 |
| $2$ | $(0,0),(1,2),(2,1)$ | 否 |
询问 2：
| 图的编号 | 边集 | 图是否连通 |
| :------: | :-----------------------: | :--------: |
| $0$ | $(0,0),(1,0),(2,0),(3,0)$ | 是 |
| $1$ | $(0,0),(1,1),(2,2),(3,3)$ | 否 |
| $2$ | $(0,0),(1,2),(2,0),(3,2)$ | 是 |
| $3$ | $(0,0),(1,3),(2,2),(3,1)$ | 否 |
| $4$ | $(0,0),(1,0),(2,0),(3,0)$ | 是 |
询问 3：
| 图的编号 | 边集 | 图是否连通 |
| :------: | :-----------------------: | :--------: |
| $0$ | $(0,0),(1,0),(2,0),(3,0),(4,0)$ | 是 |
| $1$ | $(0,0),(1,1),(2,2),(3,3),(4,4)$ | 否 |
| $2$ | $(0,0),(1,2),(2,4),(3,1),(4,3)$ | 否 |
| $3$ | $(0,0),(1,3),(2,1),(3,4),(4,2)$ | 否 |
| $4$ | $(0,0),(1,4),(2,3),(3,2),(4,1)$ | 否 |
| $5$ | $(0,0),(1,0),(2,0),(3,0),(4,0)$ | 是 |
所以答案分别为 $1, 3, 2$。
---
**【数据规模与约定】**
**本题开启捆绑测试。**
| $\text{Subtask}$ | 数据范围 | 分数 |
| :---: | :---: | :---: |
| $1$ | $n,m\le 200$ | $15$ |
| $2$ | $n,m\le 3000$ | $30$ |
| $3$ | $n,m\le 10^7$ | $15$ |
| $4$ | $n\le 3000,m \le10^{14}$ | $15$ |
| $5$ | $n,m\le 10^{14}$ | $25$ |
- 对于 $100\%$ 的数据，保证 $1\le T\le 5,1\le n,m\le 10^{14}$。