Crypto-Number

shefin Long Practice Sessions on...
Limits 2s, 512 MB

Walt and Gus have a great rivalry. Recently Gus has developed a cryptographic system. Walt is trying to crack it. While trying, he has found out that there is an array C of integers lying under the cryptographic system. Walt needs some information about the array C.

Walt has developed an algorithm to generate random integers. He calls the random integers generated by this algorithm as "Crypto-Number". The algorithm is as follows:

  1. Initially, the "Crypto-Number" is = 1.
  2. Walt chooses two integers rr, pp - both greater than 1 randomly. Then he multiplies the "Crypto-Number" with rpr^p.
  3. The result of the multiplication is the new value of "Crypto-Number".
  4. He repeats the steps 2 and 3 for a random amount of time.

It is guaranteed that the generated "Crypto-Number" follows this constraint: 4Crypto-Number10124 ≤ \text{Crypto-Number} ≤ 10^{12}.

Lets simulate the algorithm:

Step 1: The "Crypto-Number" = 1.

Step 2: Let, Walt chooses 81, 3 as rr, pp respectively. Result of multiplication is 1×813=5314411 \times 81^3 = 531441.

Step 3: The new value of "Crypto-Number" = 531441.

If Walt repeats the steps 2 and 3 again:

Step 2: Let, Walt chooses 6, 5 as rr, pp respectively this time. Result of multiplication is 531441×65=4132485216531441×6^5 = 4132485216.

Step 3: The new value of "Crypto-Number" = 4132485216.

And so on.

Now Walt wants to know, for a Crypto-Number kk, how many integers are in the array CC such that kk is completely divisible by them.

Input

The first line of the input contains an integer NN (1N1061 ≤ N ≤ 10^6), the size of the array CC. The next line will contain NN space-separated integers CiC_i (1Ci10121 ≤ C_i ≤ 10^{12}) - the elements of the array CC.

The next line contains an integer QQ (1Q1041 ≤ Q ≤ 10^4), the number of the queries. In each of the next QQ lines, there will be an integer kk (4k10124 ≤ k ≤ 10^{12}) - the "Crypto-Number".

Output

For each query, print in this format in a single line (without quotes): “Query x: y”, where xx is the number of the query and yy is the number of the integers in the array CC, which integers can completely divide kk.

Sample

InputOutput
6
1 8 4 18 13 8
4
16
36
8
169
Query 1: 4
Query 2: 3
Query 3: 4
Query 4: 2

In the first query, the integers in index 0, index 1, index 2 and index 5 in array CC completely divide 16. That is to say, the 4 integers in array CC: 1, 8, 4, 8 completely divide 16.


Submit

Login to submit.

Statistics

16% Solution Ratio
DraakKrijgerFCEarliest, Mar '20
Gias_UddinFastest, 0.4s
quachanhLightest, 33 MB
Yasir_ArafatShortest, 986B
Toph uses cookies. By continuing you agree to our Cookie Policy.