Given a sequence of integers $*a*_{1}, ..., *a*_{*n*}$ and $*q*$ queries $*x*_{1}, ..., *x*_{*q*}$ on it. For each query $*x*_{*i*}$ you have to count the number of pairs $(*l*, *r*)$ such that $1 ≤ *l* ≤ *r* ≤ *n*$ and $*gcd*(*a*_{*l*}, *a*_{*l* + 1}, ..., *a*_{*r*}) = *x*_{*i*}$.

is a greatest common divisor of $*v*_{1}, *v*_{2}, ..., *v*_{*n*}$, that is equal to a largest positive integer that divides all $*v*_{*i*}$.

Input

The first line of the input contains integer $*n*$, ($1 ≤ *n* ≤ 10^{5}$), denoting the length of the sequence. The next line contains $*n*$ space separated integers $*a*_{1}, ..., *a*_{*n*}$, ($1 ≤ *a*_{*i*} ≤ 10^{9}$).

The third line of the input contains integer $*q*$, ($1 ≤ *q* ≤ 3 × 10^{5}$), denoting the number of queries. Then follows $*q*$ lines, each contain an integer $*x*_{*i*}$, ($1 ≤ *x*_{*i*} ≤ 10^{9}$).

Output

For each query print the result in a separate line.