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 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

    Discussion

    Statistics


    83% Solution Ratio

    naeem4265Earliest, 2w ago

    FrdhsnFastest, 0.1s

    AlfehsaniLightest, 11 MB

    FrdhsnShortest, 411B

    Submit

    Login to submit

    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.