题目背景

upd 2023.1.22：新增一组 Hack 数据 by

远在哞利坚的 Bessie 也要在新春之际走亲访友！为了打发时间，她常和 Farmer John 玩一个有趣的数字游戏。

题目描述

Farmer John 有一个集合 $S$，集合初始为 $\{2,3,4,...,N\}$。

对于两个在集合 $S$ 内的正整数 $p,q$，我们称它们为「一对好数」当且仅当 $p^k=q(k\ge 2\land k\in\N)$。

我们将每个 $S$ 中的数看成一张无向图中的节点，对于每一对「好数」，我们在这两个数间连一条无向边。

Farmer John 会进行 $Q$ 次操作，操作有以下两种：

1. 给出 $x$，询问结点 $x$ 所在的连通块大小。
2. 给出 $x$，从 $S$ 中移除 $x$。与此同时，无向图中的结点 $x$ 也被移除。

由于 Bessie 的速度太慢了，她想要你来帮忙。

输入格式

第 $1$ 行 $2$ 个正整数，$N,Q$。

接下来 $Q$ 行，每行一个正整数，$op_i,x_i$。 其中，$op_i$ 表示操作的序号。

数据保证 $x_i$ 在集合 $S$ 中。

输出格式

对于操作 $1$，每行输出一个正整数，表示询问的答案。

30 6
1 6
1 4
2 9
1 3
2 2
1 16

1
4
2
2

提示

【样例解释】

这是原始无向图（上面一排都是孤点）：

这是进行第一次操作 $2$ 后的无向图（删除了结点 $9$）：

这是进行第二次操作 $2$ 后的无向图（删除了结点 $2$）：

【数据范围】

全部数据满足：

• $2\le N \le 10^{18}$
• $1\le Q \le 10^6$
• $x_i\in S$
• $op_i \in \{1,2\}$

测试点 $1\sim2$ 另外满足 $2\le N \le 10^5$，$1\le Q \le 10^4$。

测试点 $3\sim4$ 另外满足所有 $x_i=m^{p_i}$，其中 $m$ 为一满足 $m\ge 2 \land m\in \N$ 的常数。

测试点 $5\sim10$ 没有额外限制。