Here is another task for you, prepared by Monk himself. So, this is how it goes :

Given an integer array A of size N, Monk needs you to answer T queries for him. In each query, he gives you 2 integers P and Q. In response to each of these queries, you need to tell Monk the count of numbers in array A. that are either divisible by P, Q, or both.

Can you cope with this ?

Video approach to solve this question: here

Input Format :

The first line contains a single integer N denoting the size of array A. The next line contains N space separated integers, where the \(i^{th}\) integer denotes \(A[i]\).

The next line contains a single integer T denoting the number of queries Monk poses to you. Each of the next T lines contains 2 space separated integers P and Q.

Output Format :

For each query, print the answer on a new line.

Constraints :

\( 1 \le N \le 2 \times 10^5 \)

\( 1 \le A[i] \le 2 \times 10^5 \)

\( 1 \le T \le 2 \times 10^5 \)

\( 1 \le P, Q \le 2 \times 10^5 \)