题目描述

美丽区间是这样的一组区间：$[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$ 属于第几个美丽区间。

10
3
123
33
10

11
3
1

提示

样例说明

• 第 $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$。