Given a sequence of integers a1, ..., an and q queries x1, ..., xq on
it. For each query xi you
have to count the number of pairs (l, r)such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, ..., ar) = xi.

 is
a greatest common divisor of v1, v2, ..., vn,
that is equal to a largest positive integer that divides all vi.

The first line of the input contains integer n, (1 ≤ n ≤ 105),
denoting the length of the sequence. The next line contains n space separated integers a1, ..., an,
(1 ≤ ai ≤ 109).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 105),
denoting the number of queries. Then follows q lines, each contain an integer xi,
(1 ≤ xi ≤ 109).

For each query print the result in a separate line.