P8954 "VUSC" Math Game

**upd 2023.1.22**: Added one set of hack testdata by @[MCRS_lizi](https://www.luogu.com.cn/user/585805). Bessie, far away in Moo-lica, also wants to visit friends and relatives during the Spring Festival. To kill time, she often plays an interesting number game with Farmer John.

Farmer John has a set $S$, initially $\\{2,3,4,\\ldots,N\\}$. For two positive integers $p, q$ **in the set $S$**, we call them "a pair of good numbers" if and only if $p^k = q \\ (k\\ge 2 \\land k\\in\\N)$. We treat each number in $S$ as a node in an **undirected graph**. For each pair of "good numbers", we add an undirected edge between these two numbers. Farmer John will perform $Q$ operations of the following two types: 1. Given $x$, ask for the size of the connected component containing node $x$. 2. Given $x$, remove $x$ from $S$. **At the same time, node $x$ in the undirected graph is also removed.** Since Bessie is too slow, she wants you to help.

The first line contains two positive integers $N, Q$. The next $Q$ lines each contain two positive integers $op_i, x_i$. Here, $op_i$ denotes the type of the operation. **It is guaranteed that $x_i$ is in the set $S$.**

For each operation of type $1$, output one positive integer per line, which is the answer to the query.

#### Sample Explanation This is the original undirected graph (all nodes in the top row are isolated nodes):  This is the undirected graph after the first type $2$ operation (node $9$ is deleted):  This is the undirected graph after the second type $2$ operation (node $2$ is deleted):  --- #### Constraints All testdata satisfy: - $2\\le N \\le 10^{18}$ - $1\\le Q \\le 10^6$ - $x_i\\in S$ - $op_i \\in \\{1,2\\}$ Test points $1\\sim 2$ additionally satisfy $2\\le N \\le 10^5$, $1\\le Q \\le 10^4$. Test points $3\\sim 4$ additionally satisfy that all $x_i = m^{p_i}$, where $m$ is a **constant** satisfying $m\\ge 2 \\land m\\in \\N$. Test points $5\\sim 10$ have no additional constraints. Translated by ChatGPT 5