Yet Another Hello World

tahsin_protik Replay of Ada Lovelace Na...
Limits 2s, 256 MB

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

The company has already built MMdecryption systems. Each decryption system consists of an integer key, did_i.

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

The ithi^{th} decryption system can decrypt the encrypted message, eje_j if it holds the following condition:

  • The encrypted message, eje_j is not divisible by the key of the decryption system, did_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 QQ queries. Each of the queries will consist of an encrypted form of the message “Hello World”, eje_j generated by jthj^{th} encryption system. Determine the acceptance of that encryption system.

Input

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

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

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

Each of the next QQ lines contains eje_j, the encrypted message generated by the jthj^{th} encryption system.

Constraints

1M1061 \leq M \leq 10^6

1di1061 \leq d_i \leq 10^6

1Q1061 \leq Q \leq 10^6

1ej1061 \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

Submit

Login to submit.

Contributors

Statistics

83% Solution Ratio
naeem4265Earliest, 10M ago
Mushfiqur05Fastest, 0.1s
AlfehsaniLightest, 11 MB
FrdhsnShortest, 411B
Toph uses cookies. By continuing you agree to our Cookie Policy.