Given a sequence of integers a₁,...,a_n and q queries x₁,...,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₁,v₂,...,v_n, that is equal to a largest positive integer that divides all v_i.

The first line of the input contains integer n, (1≤n≤10⁵), denoting the length of the sequence. The next line contains n space separated integers a₁,...,a_n, (1≤a_i≤10⁹).

The third line of the input contains integer q, (1≤q≤3×10⁵), denoting the number of queries. Then follows q lines, each contain an integer x_i, (1≤x_i≤10⁹).

For each query print the result in a separate line.