题目描述

本题中，字符串下标从 $1$ 开始。称 $|S|$ 为字符串 $S$ 的长度（字符个数）。

字符串 $S$ 的一个子串是选取一对 $1\le l\le r\le |S|$，然后将 $S_l,S_{l+1},\ldots, S_r$ 拼接得到的字符串，记为 $S[l\ldots r]$。例如，若字符串 $S$ 是 yummy，那么 $S[2\ldots 4]$ 是 umm。

---

小 L 说了一个字符串 $S$，其中包含大写或小写字母。

小 X 把这个字符串录成了视频，但是为了保证视频内容积极向上，她要对视频进行剪辑，使其不包含否定词 not。具体地，每一轮剪辑找到 $S$ 中所有子串 not，去掉这些子串，把剩下内容拼在一起；然后检查新子串是否含有 not，如有，则再剪辑一轮，直到没有 not 为止。

例如，IcannototnAKIOI 经过第一轮剪辑会变成 IcanotnAKIOI（剪掉 $S[5\ldots 7]$），第二轮剪辑会变成 IcanAKIOI（剪掉 $S[4\ldots 6]$），剪辑了两轮。

给出字符串 $S$，请先输出剪辑后的结果，然后输出剪辑轮数。

输入格式

输入的第一行有一个自然数 $T$，表示这是第几个测试点，特别地，样例对应 $T=0$。

第二行有一行一个字符串 $S$，表示小 L 说的话。

输出格式

输出的第一行为一个字符串表示剪辑后的结果。

第二行输出一个整数，表示剪辑轮数。

0
IcannototnAKIOI

IcanAKIOI
2

0
nnototnononotttNOT

NOT
3

0
not

1

提示

【样例 1 解释】

该样例即为题目所描述的情形。

【样例 2 解释】

nnototnononotttNOT 在第一轮剪辑后，变成了 notnonottNOT。

第二轮剪辑后，变成了 notNOT。

第三轮剪辑后，变成了 NOT。

【样例 3 解释】

注意，哪怕剪辑完了啥也不剩，也要输出一个换行。

【数据范围】

本题共有 $10$ 个测试点。

• 测试点 $1$ 保证剪辑轮数为 $0$。
• 测试点 $2,3$ 保证剪辑轮数为 $1$。
• 测试点 $4,5,6$ 保证剪辑轮数为 $8$。（提示：如果你会求一般情况下的剪辑结果，但不会计算剪辑轮数，可以拿这些部分分。）

对于全部测试点，保证 $S$ 非空且仅含大写或小写字母，同时长度不超过 $100$。