Question
Prime Count in Subarray
You are given an array of KaTeX can only parse string typed expression integers. Your task is to answer KaTeX can only parse string typed expression queries. Each query consists of two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. For each query, count how many prime numbers are present in the subarray from index KaTeX can only parse string typed expression to KaTeX can only parse string typed expression (inclusive).
A prime number is a positive integer greater than KaTeX can only parse string typed expression that has exactly two distinct positive divisors: KaTeX can only parse string typed expression and itself.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the elements of the array.
The third line contains a single 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 — the range of the query (0-based indexing).
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the elements of the array.
The third line contains a single 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 — the range of the query (0-based indexing).
Output
For each query, print a single integer — the number of prime numbers in the subarray from KaTeX can only parse string typed expression to KaTeX can only parse string typed expression.
Example
Input
6
1 2 3 4 5 6
3
0 2
1 4
3 5
Output
2
3
1
Explanation
Query (0, 2) → Elements: 1, 2, 3 → Prime numbers: 2, 3 → Count = 2
Query (1, 4) → Elements: 2, 3, 4, 5 → Prime numbers: 2, 3, 5 → Count = 3
Query (3, 5) → Elements: 4, 5, 6 → Prime number: 5 → Count = 1
6
1 2 3 4 5 6
3
0 2
1 4
3 5
Output
2
3
1
Explanation
Query (0, 2) → Elements: 1, 2, 3 → Prime numbers: 2, 3 → Count = 2
Query (1, 4) → Elements: 2, 3, 4, 5 → Prime numbers: 2, 3, 5 → Count = 3
Query (3, 5) → Elements: 4, 5, 6 → Prime number: 5 → Count = 1