Crypto-Number

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 $r^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: $4 ≤ \text{Crypto-Number} ≤ 10^{12}$.

Lets simulate the algorithm:

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

Step 2: Let, Walt chooses 81, 3 as $r$, $p$ respectively. Result of multiplication is $1 \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 $r$, $p$ respectively this time. Result of multiplication is $531441×6^5 = 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$ ($1 ≤ N ≤ 10^6$), the size of the array $C$. The next line will contain $N$ space-separated integers $C_i$ ($1 ≤ C_i ≤ 10^{12}$) - the elements of the array $C$.

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

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

Input	Output
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 $C$ completely divide 16. That is to say, the 4 integers in array $C$: 1, 8, 4, 8 completely divide 16.