zeroes

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 ≤ 10^5
2 ≤ X ≤ 10^5

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 i^th of them, output the answer to the i^th query.

SAMPLE INPUT
4
3 4 1 1 
1
2

SAMPLE OUTPUT
2

Explanation

The value of P is 4 * 3 * 1 * 1 =  12. 12 in base 2 representation is "1100" which has 2 trailing zeroes.

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics


Solutions: