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\)