在编号为 x \ (x \ne 0) 的图中，每一个点都只会连出一条边，而编号为 0 的点总是和自己连边，这意味着有效的边至多有 n - 1 条。而这张图要求连通，那么这张图一定是一棵树，n - 1 条边都是有效的，具体地，没有重边和环。
我们指定 (i \cdot x) \bmod n 是 i 的父亲，那么这棵树就会呈现以编号为 0 的点为根的形态。这是因为除编号为 0 的点都没有自环，向父亲回溯时只有走到编号为 0 的点才会停止。在这个形态下观察这棵树，指定根结点 0 在第 0 层，则对于第 k 层的点 i，有 i \cdot x ^ k \equiv 0 \pmod n。
因此问题转化为对于 x \in [1, m]，有哪些 x 满足对于任意 i \in [1, n - 1] 都可以找到一个最小的 k 使得 i \cdot x ^ k \equiv 0 \pmod n。
结论是当且仅当 x 是 n 质因数的乘积的倍数时满足要求。下面给出证明。
由唯一分解定理，设 n = \prod _ {i = 1} ^ {s} p _ i ^ {r _ i}（其中 p 为质数），记 t = \prod _ {i = 1} ^ {s} p _ i，不妨设 x = c \cdot t。
必要性：一定存在 i \in [1, n - 1] 且 i \perp n（如 i = n - 1）。若 x \ne c \cdot t，则 n 有 i \cdot x ^ k 所没有的质因子，所以 i \cdot x ^ k \equiv 0 \pmod n 总不成立。
充分性：x = c \cdot t 时，k = \max _ {i = 1} ^ {s} \{r _ i \} 时显然满足，不断枚举 k \gets k - 1 直到 i \cdot x ^ {k - 1} \equiv 0 \pmod n 不成立即可找到最小的 k。
将 $n$ 分解质因数的方法可以参考 [OI Wiki](https://oi-wiki.org/math/number-theory/pollard-rho/)，本题中 $O (\sqrt n)$ 的朴素方法即可通过，这样最终的时间复杂度为 $O(T \sqrt n)$。
## 实现
```cpp
#include <iostream>
long long f(long long n) // n 所有质因数的乘积
{
long long res = 1;
for (int i = 2; 1ll * i * i <= n; i++)
{
if (n % i == 0)
res *= i;
while (n % i == 0)
n /= i;
}
if (n != 1)
res *= n;
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
while (t--)
{
long long n, m;
std::cin >> n >> m;
std::cout << m / f(n) + 1 << "\n";
}
return 0;
}
```