# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Yet Another Hello World

By tahsin_protik · Limits 2s, 256 MB

The greatest company, Pied Piper, is developing encryption systems.

The company has already built $M$decryption systems. Each decryption system consists of an integer key, $d_i$.

After developing an encryption system, it will encrypt the message “Hello World”. The encrypted message will be an integer, $e_j$. Then they will check the acceptance of that encryption system.

The $i^{th}$ decryption system can decrypt the encrypted message, $e_j$ if it holds the following condition:

• The encrypted message, $e_j$ is not divisible by the key of the decryption system, $d_i$.

The acceptance of an encryption system is the number of decryption systems that can decrypt the encrypted form of the message “Hello World” generated by it.

There will be $Q$ queries. Each of the queries will consist of an encrypted form of the message “Hello World”, $e_j$ generated by $j^{th}$ encryption system. Determine the acceptance of that encryption system.

## Input

The first line contains one integer, $M$ the number of decryption systems.

The second line consists of $M$ space-separated integers, $d_i$, the key for each decryption system $1 \leq i \leq M$.

The third line contains an integer, $Q$, the number of queries.

Each of the next $Q$ lines contains $e_j$, the encrypted message generated by the $j^{th}$ encryption system.

### Constraints

$1 \leq M \leq 10^6$

$1 \leq d_i \leq 10^6$

$1 \leq Q \leq 10^6$

$1 \leq e_j \leq 10^6$

## Output

For each query, output the acceptance of the corresponding encryption system.

## Sample

InputOutput
2
2 5
3
7
8
10

2
1
0


### Statistics

83% Solution Ratio

naeem4265Earliest, 2w ago

FrdhsnFastest, 0.1s

AlfehsaniLightest, 11 MB

FrdhsnShortest, 411B

### Editorial

The problem wants the number of decryption system which doesn’t divide the encrypted message of a ce...

Toph uses cookies. By continuing you agree to our Cookie Policy.