P12254 [蓝桥杯 2024 国 Java B] 美丽区间

美丽区间是这样的一组区间：$[L_1, R_1]$、$[L_2, R_2]$、$[L_3, R_3] \dots$。构造美丽区间需要满足以下条件： 1. $L_1 = 1$； 2. $L_i \leq R_i$； 3. $R_i - L_i \geq K$； 4. 对于任意的 $i > 1$，有 $L_i = R_{i-1} + 1$； 5. $\gcd(L_i, R_i) = 1$，其中 $\gcd$ 指两个数的最大公约数； 6. 在满足上述条件的情况下，$L_i$、$R_i$ 之间的差尽可能的小。

第一行输入一个整数 $K$。 第二行输入一个整数 $T$，表示有 $T$ 组测试用例。 接下来 $T$ 行，每行输入一个整数 $n$。

对每个输入的整数 $n$，输出一行，包含一个整数，表示 $n$ 属于第几个美丽区间。

### 样例说明 - 第 $1$ 个美丽区间为：$[1, 11]$。 - 第 $2$ 个美丽区间为：$[12, 23]$。 - 第 $3$ 个美丽区间为：$[24, 35]$。 - …… - 第 $11$ 个美丽区间为：$[120, 131]$。 ### 评测用例规模与约定 - 对于 $60\%$ 的评测用例：$1 \leq T \leq 10^3$，$1 \leq K \leq 10^6$，$1 \leq n \leq 10^6$。 - 对于 $100\%$ 的评测用例：$1 \leq T \leq 10^6$，$1 \leq K \leq 10^6$，$1 \leq n \leq 10^6$。