#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
typedef long long ll;
int a[100005];
int sieve[1000005];
vector<int>tree[1000005];
bool visited[1000005];
vector<int>factors[1000005];
void construct(int l,int r,int si)
{
if(l>r)
return ;
if(l==r)
{
tree[si]=factors[l];
return ;
}
int mid=(l+r)/2;
construct(l,mid,si*2+1);
construct(mid+1,r,si*2+2);
merge(all(tree[si*2+1]),all(tree[si*2+2]),back_inserter(tree[si]));
for(int i=0;i<tree[si].size();i++)
printf("%d ",tree[si][i]);
printf("\n");
}
int query(int l,int r,int ql,int qr,int k1,int k2,int si)
{
if(r<ql||l>qr)
{
// cout<<"si here 1 "<<si<<endl;
return 0;
}
if(l>=ql&&r<=qr)
{
//c//out<<"si here 2 "<<si<<endl;
int ans1=lower_bound(tree[si].begin(),tree[si].end(),k1)-tree[si].begin();
int ans2=upper_bound(tree[si].begin(),tree[si].end(),k2)-tree[si].begin();
return ans2-ans1;
}
int mid=(l+r)/2;
// cout<<"si here 3 "<<si<<endl;
return query(l,mid,ql,qr,k1,k2,si*2+1)+query(mid+1,r,ql,qr,k1,k2,si*2+2);
}
void prime_factor(int x,int idx)
{
while(x!=1)
{
factors[idx].pb(sieve[x]);
x/=sieve[x];
}
}
int main()
{
int n,q,l,r,x,y;
cin>>n;
for(int i=2;i*i<=1000001;i++)
{
if(visited[i])
continue;
for(int j=i*i;j<=1000001;j+=i)
{
visited[j]=true;
sieve[j]=i;
}
}
for(int i=2;i<=1000001;i++){
if(visited[i]==false)
sieve[i]=i;
}
for(int i=0;i<n;i++)
{
cin>>a[i];
prime_factor(a[i],i);
}
cin>>q;
construct(0,n-1,0);
for(int i=0;i<q;i++)
{
cin>>l>>r>>x>>y;
int ans=query(0,n-1,l-1,r-1,x,y,0);
// cout<<ans<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCnR5cGVkZWYgbG9uZyBsb25nIGxsOwppbnQgYVsxMDAwMDVdOwppbnQgc2lldmVbMTAwMDAwNV07CnZlY3RvcjxpbnQ+dHJlZVsxMDAwMDA1XTsKYm9vbCB2aXNpdGVkWzEwMDAwMDVdOwp2ZWN0b3I8aW50PmZhY3RvcnNbMTAwMDAwNV07CnZvaWQgY29uc3RydWN0KGludCBsLGludCByLGludCBzaSkKewogICAgaWYobD5yKQogICAgICAgIHJldHVybiA7CglpZihsPT1yKQoJewoJCXRyZWVbc2ldPWZhY3RvcnNbbF07CgkJCgkJcmV0dXJuIDsKCX0KCWludCBtaWQ9KGwrcikvMjsKIAoJY29uc3RydWN0KGwsbWlkLHNpKjIrMSk7Cgljb25zdHJ1Y3QobWlkKzEscixzaSoyKzIpOwogCgltZXJnZShhbGwodHJlZVtzaSoyKzFdKSxhbGwodHJlZVtzaSoyKzJdKSxiYWNrX2luc2VydGVyKHRyZWVbc2ldKSk7Cglmb3IoaW50IGk9MDtpPHRyZWVbc2ldLnNpemUoKTtpKyspCgkJICBwcmludGYoIiVkICIsdHJlZVtzaV1baV0pOwoJCSAgcHJpbnRmKCJcbiIpOwogCn0KaW50IHF1ZXJ5KGludCBsLGludCByLGludCBxbCxpbnQgcXIsaW50IGsxLGludCBrMixpbnQgc2kpCnsKIAoJaWYocjxxbHx8bD5xcikKCXsKCSAvLyAgIGNvdXQ8PCJzaSBoZXJlIDEgIjw8c2k8PGVuZGw7CgkJcmV0dXJuIDA7Cgl9CglpZihsPj1xbCYmcjw9cXIpCgl7CiAgICAgICAgLy9jLy9vdXQ8PCJzaSBoZXJlIDIgIjw8c2k8PGVuZGw7CgkJaW50IGFuczE9bG93ZXJfYm91bmQodHJlZVtzaV0uYmVnaW4oKSx0cmVlW3NpXS5lbmQoKSxrMSktdHJlZVtzaV0uYmVnaW4oKTsKCQlpbnQgYW5zMj11cHBlcl9ib3VuZCh0cmVlW3NpXS5iZWdpbigpLHRyZWVbc2ldLmVuZCgpLGsyKS10cmVlW3NpXS5iZWdpbigpOwoJCXJldHVybiBhbnMyLWFuczE7Cgl9CglpbnQgbWlkPShsK3IpLzI7CiAgLy8gIGNvdXQ8PCJzaSBoZXJlIDMgIjw8c2k8PGVuZGw7CglyZXR1cm4gcXVlcnkobCxtaWQscWwscXIsazEsazIsc2kqMisxKStxdWVyeShtaWQrMSxyLHFsLHFyLGsxLGsyLHNpKjIrMik7CiAKfQp2b2lkIHByaW1lX2ZhY3RvcihpbnQgeCxpbnQgaWR4KQp7Cgl3aGlsZSh4IT0xKQoJewoJCWZhY3RvcnNbaWR4XS5wYihzaWV2ZVt4XSk7CgkJeC89c2lldmVbeF07Cgl9Cn0KaW50IG1haW4oKQp7CglpbnQgbixxLGwscix4LHk7CgljaW4+Pm47CiAKCWZvcihpbnQgaT0yO2kqaTw9MTAwMDAwMTtpKyspCgl7CgkJaWYodmlzaXRlZFtpXSkKCQkJY29udGludWU7CgkJZm9yKGludCBqPWkqaTtqPD0xMDAwMDAxO2orPWkpCgkJewoJCQl2aXNpdGVkW2pdPXRydWU7CgkJCXNpZXZlW2pdPWk7CgkJfQogCgl9Cglmb3IoaW50IGk9MjtpPD0xMDAwMDAxO2krKyl7CgkJaWYodmlzaXRlZFtpXT09ZmFsc2UpCgkJc2lldmVbaV09aTsKCX0KCWZvcihpbnQgaT0wO2k8bjtpKyspCgl7CgkJY2luPj5hW2ldOwoJCXByaW1lX2ZhY3RvcihhW2ldLGkpOwoJfQoJY2luPj5xOwoJY29uc3RydWN0KDAsbi0xLDApOwoJZm9yKGludCBpPTA7aTxxO2krKykKCXsKCQljaW4+Pmw+PnI+Png+Pnk7CgkJaW50IGFucz1xdWVyeSgwLG4tMSxsLTEsci0xLHgseSwwKTsKCS8vCWNvdXQ8PGFuczw8ZW5kbDsKCX0KCXJldHVybiAwOwp9CiA=