问题3127--字母圣诞树

3127: 字母圣诞树

时间限制: 1 Sec  内存限制: 256 MB
提交: 487  解决: 82
[状态] [讨论版] [提交] [命题人:]
题目描述
圣诞节当天小 Y 发现自己家里突然出现一棵圣诞树,圣诞树上挂着各种小写英文字母,用一个字符串 s[1],s[2]…s[n] 表示圣诞树上挂的全部字母。现在小 Y 想把树上所有字母都换成同一个字符c,
在一次操作中,你可以选择一个数字 x(1<=x<=n),并将每个不能被 x 整除的位置 i(i%x!= 0)所对应的字符 s[i] 替换成字符 c
聪明的你能告诉小 Y 把树上字母都换成 c 的最少操作数是多少吗?
输入
第一行包含一个整数 t ( 1 ≤ t ≤ 104 ) ---- 测试用例的数量
每个测试用例的第一行包含一个整数 n ( 3 ≤ n ≤ 3×105) 和一个小写拉丁字母 c ---- 字符串长度 s 和结果字符串应包含的字符
每个测试用例的第二行包含一个由小写拉丁字母组成的字符串 s ---- 初始字符串
保证所有测试用例的 n 之和不超过 3×105
输出
对于每个测试用例,打印一个整数 m ---- 使所有字符等于 c 所需的最少操作数
样例输入 Copy
3
4 a
aaaa
4 a
baaa
4 b
bzyx
样例输出 Copy
0
1
2 
来源/分类