#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int MAXN=111111;
int stree[MAXN<<2];
int sum[MAXN<<2];
bool nico[11111111];
void init()
{
	memset(nico,1,sizeof(nico));
	for(int i=2;i<11111111;i++)
	{
		if(nico[i])
		{
			for(int j=2*i;j<11111111;j+=i)
				nico[j]=0;
		}
	}
	nico[6]=1;
	for(int i=2;i<11111111;i<<=1)
	{
		nico[i]=1;
	}
}


void pushup(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	stree[rt]=max(stree[rt<<1],stree[rt<<1|1]);
}

void build(int l,int r,int rt)
{
	stree[rt]=0;
	sum[rt]=0;
	if(l==r)
	{
		int k;
		scanf("%d",&k);
		stree[rt]=k;
		sum[rt]=nico[k]?1:0;
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}

int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		return sum[rt];
	}
	int mid=(l+r)>>1;
	int ans=0;
	if(L<=mid) ans+=query(L,R,lson);
	if(R>mid) ans+=query(L,R,rson);
	return ans;
}


void update(int L,int R,int c,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		if(stree[rt]<c)
			return;
	}
	if(l==r)
	{
		stree[rt]%=c;
		sum[rt]=nico[stree[rt]]?1:0;
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid) update(L,R,c,lson);
	if(R>mid) update(L,R,c,rson);
	pushup(rt);
}

void update3(int k,int c,int l,int r,int rt)
{
	if(l==r)
	{
		stree[rt]=c;
		sum[rt]=nico[stree[rt]]?1:0;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid) update3(k,c,lson);
	else update3(k,c,rson);
	pushup(rt);
}
int main()
{
	init();
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		build(1,n,1);
		int m;
		scanf("%d",&m);
		for(int i=0;i<m;i++)
		{
			int x,y,z;
			scanf("%d",&x);
			if(x==1)
			{
				scanf("%d%d",&y,&z);
				printf("%d\n",query(y,z,1,n,1));
			}
			else if(x==2)
			{
				int n1;
				scanf("%d%d%d",&y,&z,&n1);
				update(y,z,n1,1,n,1);
			}
			else
			{
				scanf("%d%d",&y,&z);
				update3(y,z,1,n,1);
			}
		}
	}
	return 0;
}