Practice on Toph

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

Crypto-Number

By shefin · 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 r, p - both greater than 1 randomly. Then he multiplies the “Crypto-Number” with rp.
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: 4 ≤ Crypto-Number ≤ 1012.

Lets simulate the algorithm:

Step 1: The “Crypto-Number” = 1.
Step 2:Let, Walt chooses 81, 3 as r, p respectively. Result of multiplication = 1×813 = 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 r, p respectively this time. Result of multiplication = 531441×65 = 4132485216.
Step 3: The new value of “Crypto-Number” = 4132485216.
And so on.

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

Input

The first line of the input contains an integer N, the size of the array C. The next line will contain N space-separated integers Ci - the elements of the array C.
The next line contains an integer Q, the number of the queries. In each of the next Q lines, there will be an integer k - the “Crypto-Number”.

Constraints:
1 ≤ N ≤ 106
1 ≤ Ci ≤ 1012
1 ≤ Q ≤ 104
4 ≤ k ≤ 1012

Subtask 1, For 10 points: 1 ≤ Q ≤ 10, 4 ≤ k ≤ 106

Subtask 2, For 30 points: 1 ≤ Q ≤ 104, 4 ≤ k ≤ 106

Subtask 3, For 60 points: The original constraints.

Output

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

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


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


Discussion

Statistics


14% Solution Ratio

DraakKrijgerFCEarliest, 1M ago

alamkhanFastest, 0.5s

quachanhLightest, 33 MB

DraakKrijgerFCShortest, 1956B

Submit

Login to submit