Make Them Equal

题意翻译

你有一个长度为 $n$ 的字符串 $s$（下标从 $1$ 开始）和一个字符 $c$。你可以执行若干次操作，在每次操作中你可以选择一个数 $x(1\leqslant x\leqslant n)$，然后将 $s$ 中所有下标不能被 $x$ 整除的位置上面的字符替换成 $c$。求使得最终得到的字符串 $s$ 中仅包含字符 $c$ 的最小操作次数，并给出每次操作中你选择的 $x$。 数据范围与约束： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $3\leqslant n\leqslant 3\times 10^5$。 - 字符串 $s$ 和字符 $c$ 仅由小写字母组成。 - $\sum n\leqslant 3\times 10^5$。 Translated by Eason_AC

题目描述

Theofanis has a string $ s_1 s_2 \dots s_n $ and a character $ c $ . He wants to make all characters of the string equal to $ c $ using the minimum number of operations. In one operation he can choose a number $ x $ ( $ 1 \le x \le n $ ) and for every position $ i $ , where $ i $ is not divisible by $ x $ , replace $ s_i $ with $ c $ . Find the minimum number of operations required to make all the characters equal to $ c $ and the $ x $ -s that he should use in his operations.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains the integer $ n $ ( $ 3 \le n \le 3 \cdot 10^5 $ ) and a lowercase Latin letter $ c $ — the length of the string $ s $ and the character the resulting string should consist of. The second line of each test case contains a string $ s $ of lowercase Latin letters — the initial string. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case, firstly print one integer $ m $ — the minimum number of operations required to make all the characters equal to $ c $ . Next, print $ m $ integers $ x_1, x_2, \dots, x_m $ ( $ 1 \le x_j \le n $ ) — the $ x $ -s that should be used in the order they are given. It can be proved that under given constraints, an answer always exists. If there are multiple answers, print any.

输入输出样例

输入样例 #1

3
4 a
aaaa
4 a
baaa
4 b
bzyx

输出样例 #1

0
1
2
2 
2 3

说明

Let's describe what happens in the third test case: 1. $ x_1 = 2 $ : we choose all positions that are not divisible by $ 2 $ and replace them, i. e. bzyx $ \rightarrow $ bzbx; 2. $ x_2 = 3 $ : we choose all positions that are not divisible by $ 3 $ and replace them, i. e. bzbx $ \rightarrow $ bbbb.