A cloud infrastructure company stores the current load of N servers in an array.
The monitoring team receives several audit queries. Each query asks about a continuous range of servers from index L to index R.
For a selected range, the team considers every pair of servers (i, j) such that:
L <= i < j <= R
A pair is considered valid if the combined load of the two servers can be written as the sum of one or more prime numbers.
In other words, for a pair (i, j) to be valid, there must exist prime numbers p1, p2, ..., pk, where k >= 1, such that:
A[i] + A[j] = p1 + p2 + ... + pk
The same prime number may be used multiple times.
For every query, print the number of valid pairs in the given range.
The first line contains an integer KaTeX can only parse string typed expression — the number of test cases.
For each test case, the first line contains an integer KaTeX can only parse string typed expression — the number of servers.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the server load values.
The next line contains an integer KaTeX can only parse string typed expression — the number of queries.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
For each query, print a single integer — the number of valid pairs in the given range.
Input
1
5
2 4 1 0 5
2
3 5
1 52
9For the first query, the selected values are KaTeX can only parse string typed expression. The valid pair sums are KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, so the answer is KaTeX can only parse string typed expression.
Example 2:
Input
1
4
0 0 1 2
3
1 2
1 3
2 40
0
2The first two queries contain only pairs whose sums are KaTeX can only parse string typed expression or KaTeX can only parse string typed expression. In the third query, two pairs have valid sums.
Example 3:
Input
1
6
2 3 4 5 6 7
2
1 6
2 415
3Every pair in both queried ranges has sum at least KaTeX can only parse string typed expression, so all pairs are valid.