Dreamoon 喜欢弦乐。今天他创造了一个关于弦乐的游戏:
字符串 $$$s_1, s_2, \ldots, s_n$$$ 是美丽的当且仅当对于每个 $$$1 \le i < n, s_i \ne s_{i+1}$$$。
最初,Dreamoon 有一个字符串 $$$a$$$。在每一步中,Dreamoon 都可以选择 $$$a$$$ 的一个漂亮的子字符串并将其删除。然后他应该连接剩余的字符(以相同的顺序)。
Dreamoon想要用最少的步数将$$$a$$$清空。请帮助 Dreamoon,并打印出使 $$$a$$$ 为空的最小步骤数的任意序列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 200\,000$$$),表示输入中测试用例的数量。
对于每个测试用例,都有一行包含小写拉丁字母 $$$a$$$ 的非空字符串。
所有测试用例中字符串长度的总和最多为$$$200\,000$$$。
输出
对于每个测试用例,在第一行中,您应该打印 $$$m$$$:使 $$$a$$$ 为空的最小步骤数。以下$$$m$$$行中的每一行都应包含两个整数$$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq |a|$$$),表示第$$$i$$$步骤正在删除当前字符串中索引$$$l_i$$$到$$$r_i$$$的字符。 (索引编号从 $$$1$$$ 开始)。
请注意,删除子字符串后,剩余字符的索引可能会发生变化,$$$r_i$$$ 最多应为 $$$a$$$ 的当前长度。
如果有多种可能的解决方案,您可以打印任何一个。
示例
输入 #1
4 aabbcc aaabbb aaa abacad
输出 #1
3 3 3 2 4 1 2 3 3 4 2 3 1 2 3 1 1 1 1 1 1 1 1 6