#1871. 接连不断!

接连不断!

题目描述

青蛙有 m+1m+1 个无向图,编号为 0∼m0\sim m。每个图的点集都是 VV,点集 VV 包含 nn 个点,编号为 0∼n−10\sim n-1。起初所有的图都没有边存在。

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

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

注:

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

输入格式

本题有多组数据。

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行两个整数 n,mn,m,含义同上。

输出格式

共 TT 行,每行一个整数表示答案。

样例

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

题目来源:洛谷 P10394