P10394 接连不断！

小青蛙被关进了监狱的小黑屋里，他遭受了接连不断的折磨，无论是肉体上还是精神上。 他的精神萎靡不振，他的身体行动迟缓。 有些东西被暂时的压制了，但这些东西越是被压制，它反弹时威力就越大。 他需要一个契机。

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

无

无

**【样例 #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}$。