#include<bits/stdc++.h>
#define int long long
#define R1 register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R1 int x=0,t=1;R1 char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=1e6+10;
int n,Q,num[N],cnt,tott,ans[N];
set<int>del;
struct que
{
	int op,x,fx,fy;
}q[N];
vector<int>f[N],siz[N];
int get_fx(int x)
{
	for(int i = 2;i*i*i<=x;i++){
		int t=x;
		while(t>1){
			if(t%i==0) t/=i;
			else break;
		}
		if(t==1){
			return i;
		}
	}
	int gh=sqrtl(x);
	if(gh*gh==x) return gh;
	if((gh-1)*(gh-1)==x) return gh-1;
	if((gh+1)*(gh+1)==x) return gh+1;
	return x;
}
int get_fy(int x,int base)
{
	int cntt=0;
	while(x>1)
	{
		cntt++;
		if(x%base==0){
			x/=base;
		}
		else return -1;
	}
	return cntt;
}
int find(int id,int x)
{
	if(f[id][x]==x) return x;
	return f[id][x]=find(id,f[id][x]);
}
void bin(int i,int x,int y)
{
	int dx=find(i,x),dy=find(i,y);
	if(dx==dy) return;
	f[i][dx]=dy;
	siz[i][dy]+=siz[i][dx];
	return;
}
void init()
{
	int tot=0;
	for(int i = 1;i<=Q;i++){
		num[++tot]=q[i].fx;
	}
	sort(num+1,num+1+tot);
	cnt=unique(num+1,num+1+tot)-num-1;//对所有底数离散化
	F(i,1,cnt){
		int cnt=logl(n)/logl(num[i]);//底数num[i]在n以内能连几个
		f[i].resize(cnt+1),siz[i].resize(cnt+1);
		F(j,1,cnt) f[i][j]=j,siz[i][j]=1;
		int tmp=1;
		for(int j = 1;j<=cnt/2;j++){
			tmp*=num[i];
			if(del.count(tmp)) continue;
			int cur=tmp;
			for(int k = 2;k<=cnt/j;k++){
				cur*=tmp;
				if(del.count(cur)) continue;
				bin(i,j,j*k);//连边
			}
		}
	}
}
void calc()
{
	for(int i = Q;i>=1;i--){
		int base=q[i].fx,power=q[i].fy;
		int id=lower_bound(num+1,num+1+cnt,base)-num;
		if(q[i].op==1){
			ans[++tott]=siz[id][find(id,power)];
			continue;
		}
		del.erase(q[i].x);
		int cnt=logl(n)/logl(num[id]);
		int tmp=1;
		for(int j = 2;j<=cnt/power;j++){//向底数相同，指数是power的倍数的点连边
			tmp*=q[i].x;
			if(del.count(tmp)) continue;
			bin(id,power,power*j);
		}
		tmp=1;
		for(int j = 1;j<power;j++){
			tmp*=base;
			if(del.count(tmp)) continue;
			if(power%j==0) bin(id,j,power);
		}
	}
}
signed main()
{
	n=read(),Q=read();
	F(i,1,Q){
		q[i].op=read(),q[i].x=read();
		q[i].fx=get_fx(q[i].x);
		if(q[i].op==2) del.insert(q[i].x);
		q[i].fy=get_fy(q[i].x,q[i].fx);
	}
	init();
	calc();
	for(int i = tott;i>=1;i--) cout << ans[i] << '\n';
	return 0;
}
/*

*/