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.

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<set>

 #include<string>

 //#include<pair>

 #define N 1000005

 #define M 1000005

 #define mod 1000000007

 //#define p 10000007

 #define mod2 100000000

 #define ll long long

 #define LL long long

 #define maxi(a,b) (a)>(b)? (a) : (b)

 #define mini(a,b) (a)<(b)? (a) : (b)

 using namespace std;

 int n,q;

 int a[N];

 map<int,ll>ans;

 typedef pair<int,ll>PP;

 PP save[N];

 int tot;

 int gcd(int x,int y)

 {

     if(y==)

         return x;

     return gcd(y,x%y);

 }

 void ini()

 {

     int i;

     ans.clear();

     tot=;

     for(i=;i<=n;i++){

         scanf("%d",&a[i]);

     }

 }

 void solve()

 {

     int i,j;

     int sn;

     for(i=;i<=n;i++){

         for(j=;j<tot;j++){

             save[j].first=gcd(save[j].first,a[i]);

         }

         save[tot]=make_pair(a[i],);

         tot++;

         sn=;

         for(j=;j<tot;j++){

             if(save[sn].first==save[j].first){

                 save[sn].second+=save[j].second;

             }

             else{

                 sn++;

                 save[sn]=save[j];

             }

         }

         sn++;

         tot=sn;

         for(j=;j<tot;j++){

             ans[ save[j].first ]+=save[j].second;

         }

     }

 }

 void out()

 {

     int x;

     scanf("%d",&q);

     while(q--){

         scanf("%d",&x);

         printf("%I64d\n",ans[x]);

     }

 }

 int main()

 {

     //freopen("data.in","r",stdin);

     //freopen("data.out","w",stdout);

    // scanf("%d",&T);

    // for(int ccnt=1;ccnt<=T;ccnt++)

    // while(T--)

     while(scanf("%d",&n)!=EOF)

     {

         //if(n==0 && k==0 ) break;

         //printf("Case %d: ",ccnt);

         ini();

         solve();

         out();

     }

     return ;

 }