题目背景

小青蛙被关进了监狱的小黑屋里，他遭受了接连不断的折磨，无论是肉体上还是精神上。

他的精神萎靡不振，他的身体行动迟缓。

有些东西被暂时的压制了，但这些东西越是被压制，它反弹时威力就越大。

他需要一个契机。

题目描述

青蛙有 $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$ 之间存在至少一条路径，则我们称这个图是连通的。

输入格式

本题有多组数据。

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

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

输出格式

共 $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

提示

【样例 #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}$
$5$	$n,m\le 10^{14}$	$25$

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