rt,蒟蒻基本是看着题解打的了，但是基本全部TLE（

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,l,r) for(int i=r;i>=l;i--)
#define fu(i,n) for(int i=1;i<=n;i++)
#define putC(x) {cout<<(x)<<endl;continue;}
#define putB(x) {cout<<(x)<<endl;break;}
#define putE(x) {cout<<(x)<<endl;exit(0)}
#define il inline
template<typename T> 
il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
il void read(T &x, Args &... y){ read(x);read(y...); }
#define int long long

map<int,int> mp;
set<int> st;

int p3[1000100];
int top;

int f(int x){
  int offset;
  if(mp.count(x)){
    return mp[x];
  }else if(p3[offset=lower_bound(p3+1,p3+1+top,x)-p3]==x){
    return offset;
  }else if((int)sqrtl(x)*(int)sqrtl(x)==x){
    return (int)sqrtl(x);
  }
  return x;
}

int kf(int a,int b){
  int ret=0;
  for(;a%b==0;a/=b,ret++);
  return ret;
}

main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,q;
  read(n,q);
  rep(i,2,1e6) p3[i]=i*i*i,top=i;
  rep(i,2,32000){
    int k=i;
    while(k<=n) {
      if(!mp.count(k)) mp[k]=i;
      k*=i;
    }
  }
  while(q--){
    int op,x;
    read(op,x);
    if(op==1){
      int fx=f(x),k=kf(x,fx),anc=fx;
      rep(i,1,k){
        if(k%i==0&&!st.count(anc)) break;
        anc*=fx;
      }
      int ans=0,prod=anc;
      while(prod<=n) ans+=(!st.count(prod)),prod*=anc;
      cout<<ans<<endl;
    }else {
      st.insert(x);
    }
  }
}