← 返回题目列表

Codeforces · 1594/C

C. 让他们平等

中文机器翻译题面 查看原题

Theofanis 有一个字符串 $$$s_1 s_2 \dots s_n$$$ 和一个字符 $$$c$$$。他想用最少的运算次数使字符串的所有字符都等于$$$c$$$。

在一次操作中,他可以选择一个数字 $$$x$$$ ($$$1 \le x \le n$$$),并且对于每个位置 $$$i$$$,其中 $$$i$$$ 不能被 $$$x$$$ 整除,将 $$$s_i$$$ 替换为 $$$c$$$。

找出使所有字符等于 $$$c$$$ 所需的最少操作数以及他应该在操作中使用的 $$$x$$$-s。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) 和一个小写拉丁字母 $$$c$$$ - 字符串 $$$s$$$ 的长度以及结果字符串应包含的字符。

每个测试用例的第二行包含一个由小写拉丁字母组成的字符串 $$$s$$$ — 初始字符串。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,首先打印一个整数$$$m$$$——使所有字符等于$$$c$$$所需的最少操作次数。

接下来,打印 $$$m$$$ 整数 $$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_j \le n$$$) — 应按照给定顺序使用的 $$$x$$$-s。

可以证明,在给定的约束条件下,答案总是存在的。如果有多个答案,请打印其中一个。

示例

输入 #1

3
4 a
aaaa
4 a
baaa
4 b
bzyx

输出 #1

0
1
2
2 
2 3

注意

让我们描述一下第三个测试用例中发生的情况:

1. $$$x_1 = 2$$$:我们选择所有不能被$$$2$$$整除的位置并替换它们,i。 e. bzyx $$$\rightarrow$$$ bzbx;
2. $$$x_2 = 3$$$:我们选择所有不能被$$$3$$$整除的位置并替换它们,i。 e. bzbx $$$\rightarrow$$$ bbbb。