3010: 书人

彩虹岛的史书历来是由一族人掌管的，他们被称为书人。唯有书人一族才懂得如何书写与阅读彩虹岛史书上的特殊文字，他们世代肩负着守护与传承彩虹岛历史的重任。
现任的书人是一位德高望重的长者，他每天除了要记载一些大新闻外，还要阅读与整理书籍。为了方便，他常常把书籍一本一本堆放起来。
目前，彩虹岛的藏书室共有$n$种书籍（每种书籍可能有很多本）需要书人来管理，书籍的编号为$1 \sim n$，书人常常会进行以下三种操作：

• 在书堆上放上一本编号为$x$的书
• 将书堆最上面的那本书取下来
• 将书堆恢复成第$t$次操作结束时的状态（若$t = 0$则恢复成初始状态）

由于书堆上往往被堆放了很多书，为了防止书堆倾倒，书人在执行第$3$种操作时，仍旧是通过多次的取/放一本书操作（即操作$1$、$2$）来完成的，这个过程非常繁琐。
现已知书人掌管的书种数$n$，书堆初始状态为空，书人之后要进行$m$次上述操作，他想知道对于每次操作$3$，他最少要进行几次取/放一本书的操作才能完成。

输入第一行为一个整数$T$，表示一共有$T$组测试数据。
对于每组测试数据：
第一行有两个整数$n$和$m(1 \leq n, m \leq 200000)$，表示书的种数以及书人进行的操作数。
接下来$m$行，第$i$行有以下三种情况：
$1$ $x$ 表示在书堆上放上一本编号为$x(1 \leq x \leq n)$的书。
$2$ 表示取下书堆最上面的一本书。
$3$ $t$ 表示将书堆恢复成第$t(0 \leq t < i)$次操作结束时的状态。

对于每次操作$3$，请输出一个整数表示书人完成这次操作$3$，所要进行的最少的取/放一本书操作数目。

1
2 6
1 1
1 1
2
1 2
3 2
3 0

2
2