题目背景

在古老的数学王国里，有一位智慧的老数学家，他留下了一个神秘的宝藏盒。要打开这个宝盒，需要回答一系列关于质数的问题。

国王给了你一个长度为 $n$ 的数组 $a$，里面装着一些正整数（每个数都不超过 $10^7$）。

现在有 $q$ 次查询，每次查询给出一个区间 $[x, y]$。

你需要回答：在数组 $a$ 中，有多少个无序二元组 $(a_i, a_j)$（其中 $i < j$）满足：

• $a_i$ 和 $a_j$ 都是质数；
• 并且 $a_i$ 和 $a_j$ 的值都在区间 $[x, y]$ 内（即 $x \le a_i \le y$ 且 $x \le a_j \le y$）。

只有答对所有查询，你才能获得老数学家的宝藏。请你编写程序帮助国王。

输入格式

第一行一个整数 $n$，表示数组的长度。
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组中的数。
第三行一个整数 $q$，表示查询的次数。
接下来 $q$ 行，每行两个整数 $x, y$，表示一次查询的区间（包含两端）。

输出格式

共 $q$ 行，每行一个整数，依次对应每次查询的答案。

样例

6
2 3 4 5 7 11
3
2 5
5 10
8 12

3
1
0

样例解释

• 数组中的质数有：$2, 3, 5, 7, 11$。

• 所有质数二元组（无序）：
  $(2,3), (2,5), (2,7), (2,11), (3,5), (3,7), (3,11), (5,7), (5,11), (7,11)$

• 第一次查询 $[2,5]$：质数在 $[2,5]$ 内的有 $2,3,5$ → 从这 $3$ 个数中选 $2$ 个，共 $3$ 个二元组。输出 $3$。

• 第二次查询 $[5,10]$：质数在 $[5,10]$ 内的有 $5,7$ → 共 $1$ 个二元组。输出 $1$。

• 第三次查询 $[8,12]$：质数在 $[8,12]$ 内的只有 $11$，个数为 $1$，无法构成二元组，输出 $0$。

数据范围与约定

• $1 \le n \le 10^5$
• $1 \le a_i \le 10^7$
• $1 \le q \le 10^5$
• $1 \le x \le y \le 10^9$