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, A_i, Q ≤ 10⁵
2 ≤ X ≤ 10⁵

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.