Monk and Divisor Conundrum
Tag(s):

## Easy, Factorization, Mathematics

Problem
Editorial
Analytics

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 ?

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$

SAMPLE INPUT
6
2 3 5 7 4 9
2
4 5
3 7
SAMPLE OUTPUT
2
3
Explanation

For the $1^{st}$ query in the $1^{st}$ sample, the numbers that form a part of the count are 4 and 5, present at indices 5 and 3 respectively.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

CodeMonk (Number Theory Part I)

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Math > Number Theory
• Math > Number Theory
• Math > Number Theory