You are given an array A containing N integers. Let P be the product of all the elements of A. Your task is to answer Q queries. Each query consists of a single integer X. In order to answer a query, you have to find the number of trailing 0's in P represented in base X.
For more information about base representation of a number, please refer here.
Constraints
1 ≤ N, Ai, Q ≤ 105
2 ≤ X ≤ 105
Input format
The first line contains a single integer N. The second line contains N space separated integers, representing the array A. The third line contains a single integer Q. Next Q lines follow, each containing a single integer X, denoting a single query.
Output format
Output exactly Q lines. In the ith of them, output the answer to the ith query.
The value of P is 4 * 3 * 1 * 1 = 12.
12 in base 2 representation is "1100" which has 2 trailing zeroes.
