小赵有一个字符串s1,s2,…,sn和一个字符c。他希望通过最少的操作次数将字符串中的所有字符都变成c。
在一次操作中,他可以选择一个数字x(1 ≤ x ≤ n),对于每一个位置i,如果i不能被x整除,就将si替换为c。
找到将所有字符变为c所需的最少操作次数,以及在操作中应使用的x值。并且在保证操作次数最小的情况下,所有的x的总和最大。
小赵有一个字符串s1,s2,…,sn和一个字符c。他希望通过最少的操作次数将字符串中的所有字符都变成c。
在一次操作中,他可以选择一个数字x(1 ≤ x ≤ n),对于每一个位置i,如果i不能被x整除,就将si替换为c。
找到将所有字符变为c所需的最少操作次数,以及在操作中应使用的x值。并且在保证操作次数最小的情况下,所有的x的总和最大。
第一行包含一个整数t(1 ≤ t ≤ 10^4)————测试用例的数量。
每个测试用例的第一行包含一个整数n(3 ≤ n ≤ 3 × 10^5)和一个小写字母c————字符串的长度以及要得到的目标字符。
第二行包含一个字符串s,它是初始的字符串。
保证所有测试用例中n的总和不超过3 × 10^5。
对于每个测试用例,首先输出一个整数m———— 将所有字符变成c所需的最少操作次数。
接着,输出m个整数x1, x2, …, xm— 在操作中应使用的x值,并且这m个x的总和最大。所有的x由大到小输出。
在给定的约束下,可以证明总是存在一个解。
3 4 a aaaa 4 a baaa 4 b bzyx
0 1 4 2 4 3
第三个用例中
m = 2,x1 = 3,x2 = 2两次操作可以让字符串全变成c
m = 2,x1 = 4,x2 = 3两次操作可以让字符串全变成c
但是4 + 3 > 3 + 2,所以答案是m = 2,x1 = 4,x2 = 3。