P11416 [EPXLQ2024 fall round] Simple Math Problem
题目背景
于是原先的 C 变成了 A，原先的 D 变成了 B，原先的 F 变成了 E，然后就有了这道题。
注：想拿到**快速 AK 变换奖**请在代码注释部分写明本题代码复杂度证明。
题目描述
Cute_QiQi 有一个可爱的整数 $n$。
现在，Cute_QiQi 想知道有多少个 $m \in (0,n)$，满足 $nm$ 能被 $n-m$ 整除。
输入格式
**本题单个测试点内有多组测试数据。**
第一行一个整数 $T$，表示数据组数。
以下 $T$ 行，每行一个整数 $n$。
输出格式
输出 $T$ 行，每行一个整数表示答案。
说明/提示
### 样例解释
当 $n = 114$ 时，可有 $m \in \{38,57,76,78,95,96,102,105,108,110,111,112,113\}$。
当 $n = 1919$ 时，可有 $m \in \{1558,1818,1900,1918\}$。
### 数据规模与约定
**本题采用捆绑测试与子任务依赖。**
设 $p$ 为 $n$ 质因数分解后最大的质数，$p,q$ 均为质数。
| $\text{Subtask}$ | $n \le$ | 特殊性质 | 分值 | 依赖子任务
| :-: | :-: | :-: | :-: | :-: |
| $0$ | $10^{14}$ | $n = p$ | $2$ | |
| $1$ | $10^3$ | | $7$ | |
| $2$ | $10^6$ | |$11$ | $1$ |
| $3$ | $10^9$ | |$24$ | $1,2$ |
| $4$ | $10^{14}$ | $n = pq$ | $12$ | |
| $5$ | $10^{14}$ | $p \le 10^6$ | $15$ | |
| $6$ | $10^{14}$ | | $29$ | $0,1,2,3,4,5$ |
对于所有数据，$1 \le n \le 10^{14}, 1 \le T \le 10$。