暂无测试数据。

蒜头君有一个长度为 $n$ 的数列，第 $i$ 个数为 $a_i$。花椰妹最近对质数很感兴趣，所以花椰妹向蒜头君提出了 $Q$ 个问题，对于每个问题，花椰妹想知道蒜头君的这个数列中区间 $[l,r]$ 中质数的个数。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，例如 $2,3,5,7,11,\cdots$。

输入格式

• 输入第一行一个正整数 $n$，表示蒜头君的数列长度。
• 第二行以空格隔开的 $n$ 个正整数 $a_i$，表示蒜头君的数列。
• 第三行一个正整数 $Q$，表示花椰妹的询问次数。
• 接下来 $Q$ 行，第 $i$ 行两个以空格隔开的正整数 $l,r$，表示花椰妹的询问区间。

输出格式

输出共 $Q$ 行，每行一个非负整数。第 $i$ 行的数表示花椰妹第 $i$ 次询问的结果。

数据范围

• 对于 $20\%$ 的数据，$1\leq n,Q\leq 100, 1\leq a_i \leq 10^6$；
• 对于另外 $30\%$ 的数据，$1\leq n\leq 10^4, 1\leq Q \leq 10^3,1\leq a_i \leq 10^6$；
• 对于 $100\%$ 的数据，$1\leq n \leq 10^4, 1\leq Q\leq 10^6, 1\leq a_i \leq 10^6, 1\leq l\leq r \leq n$。

注：建议使用 scanf/printf 输入输出。

8
1 2 3 4 5 6 7 8
3
1 3
2 6
1 8

2
3
4

10
2 43 45 4 234 54 65 11 79 57
5
2 4
3 8
5 10
1 3
1 10

1
1
2
2
4