#include <bits/stdc++.h>
using namespace std;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

constexpr long long N = 1e18;

unordered_set<long long> removed, visited;
constexpr int PRE_N = 1e6;
int matcher[PRE_N];
long long n;
int q;

//constexpr int NS = 1e6;
//int primes[NS];
constexpr int PCNT = 18;
int primes[18] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
long long preach[18];
int rbound[18] = {-1,1000000000,1000000,32000,4000,1000,375,180,100,65,45,35,25,20,20,20,20,20};

// Once too big, returns -1
long long fastpow(long long a, int b) {
	if (b <= 0) return 1ll;
	else if (b&1) {
		__int128 pre = fastpow(a, b-1);
		if (pre < 0) return -1;
		else {
			if (pre * a > N) return -1;
			else return (long long)(pre * a);
		}
	} else {
		__int128 pre = fastpow(a, b>>1);
		if (pre < 0) return -1;
		if (pre * pre > N) return -1;
		else return (long long)(pre * pre);
	}
}

inline int mini(int a, int b) {
	return a < b ? a : b;
} 

// Directly get division counter. Maybe memorizal search ???
void division(long long x) {
	if (removed.count(x) || visited.count(x)) {
		return;				// Unable to connect through
	}
	visited.insert(x);
	// Directly get value
	__int128 cur = x;
	while (cur <= n) {
		if ((!removed.count(cur)) && (!visited.count(cur))) {
			division(cur);
		}
		cur *= x;
	}
	// end.
	for (int i = 17; i >= 0; i--) {
		// Try primes[i]
		int pi = primes[i];
		if (x < preach[i]) continue;
		else if (x == preach[i] && (!removed.count(2))) {
			division(2);
			continue;
		}
		
		int l = 2, r, ans = 2;
		if (pi >= 18) r = 20;
		else r = rbound[pi];
		while (l <= r) {
			int mid = (l+r) >> 1;
			__int128 val = fastpow(mid, pi);
			if (val > 0 && val <= x) {
				l = mid + 1;
				ans = mid;
			} else {
				r = mid - 1;
			}
		}
		__int128 val = fastpow(ans, pi);
		if (val > 0 && val == x) {
			division(ans);
		}
	}
	
}

int main() {

//#ifdef ONLINE_JUDGE
	train();
//#endif
	
	for (int i = 0; i < 18; i++) {
		preach[i] = 1ll<<primes[i];
//		cerr<<"preach["<<i<<"]=1ll<<"<<primes[i]<<"="<<preach[i]<<endl;
	}
	
	cin>>n>>q;
	
	for (int i = 0; i < q; i++) {
		int op;
		__int128 yield,cur;
		long long x;
		int answer;
		cin>>op>>x;
		switch (op) {
			case 1:
				visited.clear();
				division(x);
				cout<<visited.size()<<'\n';
				break;
			case 2:
				removed.insert(x);
				break;
		}
	}
	
	//cout<<flush;

	return 0;
}

大致思路：对每个点 $t$ 跑 DFS（看它有哪些 $x$ 满足 $\exist k, x^k=t$），搜到点的个数一定不大于 $\log_2n$，故复杂度正确。

目前 WA on #2, #3, #4

和题解拍不出来（甚至把部分题解 hack 了）