KowerKoint 君参加了一个竞赛程序设计比赛，比赛中有如下问题：

给定一个正整数 $N$，以及一个长度为 $N$ 的正整数数列 $A=(A_1, A_2, \dots, A_N)$。请你输出 $A$ 的最大值模正整数 $m$ 的结果。

然而，KowerKoint 君错误地提交了一个代码，它输出的是 $A$ 的每个元素模 $m$ 的最大值。这个代码虽然不正确，但是由于命题人只准备了一个测试点，这个错误程序却奇迹般地得到了正确的输出。现给定命题人准备的这个测试点的 $N$ 和 $A$，并有 $Q$ 个查询。对于第 $q$ 个查询，给定 $M_q$，请你求满足 $1 \leq m \leq M_q$ 的所有 $m$ 中，使得 $A$ 的最大值模 $m$ 等于 $A$ 中的每个元素模 $m$ 的最大值的 $m$ 的个数。

输入以以下格式从标准输入读入：

$N\ A_1\ A_2\ \dots\ A_N\ Q\ M_1\ M_2\ \vdots\ M_Q$

输出 $Q$ 行，第 $q$ 行输出第 $q$ 个查询的答案。

小子任务

1.（$1$ 分）$N \leq 100$，$A_i \leq 100$
2.（$99$ 分）没有其他额外限制。

样例解释 1

对于第 $1$ 个查询，$m$ 可以为 $1,2,4$，共有 $3$ 种可能。

这个测试点符合小子任务 1 的限制。

样例解释 2

本测试点同样符合小子任务 1 的限制。

数据范围

• $1 \leq N \leq 200{,}000$
• $1 \leq N \times A_i \leq 2 \times 10^{10}$
• $1 \leq Q \leq 200{,}000$
• $1 \leq M_q \leq 10^{18}$
• 输入均为整数。

由 ChatGPT 5 翻译