You are given an array $A$ having $N$ integers and $Q$ queries. Each query is described by two integers $L$ and $R$. For each query, find the number of pairs $(i, j)$ such that $L \leq i \lt j \leq R$ and $A_i + A_j$ can be expressed as the sum of one or more prime numbers.

In the sum, you are allowed to use a prime number more than once.

Input format

• The first line of input contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integers $N$.
• The second line of each test case contains $N$ space-separated integers $A_1, A_2,\dots, A_N$.
• Then $Q$ lines follow, each containing two space-separated integers $L$ and $R$.

Output format

For each query, print the number of pairs that satisfies the given conditions in a separate line.

Constraints

$1 \leq T \leq 10 \\ 2 \leq N \leq 10^5\\ 0 \leq A_i \leq 10^5 \\ 1 \leq Q \leq 10^5 \\ 1 \leq L \leq R \leq N$