问题描述

美丽区间是这样的一组区间：$[L_1,R_1]、[L_2,R_2]、[L_3,R_3]...$ 构造美丽区间需要满足以下条件：

• $L_1=1$
• $L_i≤R_i$​
• $R_i−L_i≥K$
• 对于任意的 $i>1$，有 $L_i=R_{i-1}+1$
• $gcd(L_i,R_i)=1$，其中 $gcd$ 指两个数的最大公约数
• 在满足上述条件的情况下，$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≤T≤10^3$，$1≤K≤10^6$，$1≤n≤10^6$。

对于 $100\%$ 的评测用例：$1≤T≤10^6$，$1≤K≤10^6$，$1≤n≤10^6$。