尧老师的孩子想让尧老师陪他去游乐园玩，但是此时尧老师正在证明秦莞尔猜想。为了让孩子不再打扰他，他扔给了的孩子一个算术题，表示如果能在1S内解出就同意一起出去玩。虽然他是尧老师的孩子，但他毕竟只有三岁（如果有一分钟的话也许能解出来）。于是他求助你：

​ 定义$N=\prod_{i=0}^{n-1}p_i$ （$p_i$ 为素数且互不相同），$f(\pi,N)$ 的值为使$N|(x^{\pi}-x)$ 成立的$x$ 的个数$(0\leqslant x <N)$。$Q$ 次询问，每次询问给定一个$\pi$ ，问$f(\pi,N)$ 的值。

不超过50组数据。

每组数据第一行包含一个整数$n(0< n \leqslant 50)$ ，第二行包含$n$个整数$p_i(1<p_i<10^4)$ 。

第三行包含一个整数$Q(0<Q\leqslant 100)$ ，接下来$Q$ 行每行包含一个整数$\pi(1 \leqslant\pi \leqslant 10^9)$ 。

对于每个询问输出一个整数，输出$f(e,N)$ 的值。

注意答案可能过大，请将答案对第$1226564$ 个素数取膜后输出。

样例询问的是有多少不同的$x(0\leqslant x <6)$ ，满足$6|x^2-x$ ，显然只有$x=0,1,3,4$ 四种。