[Solution] Make Them Equal solution codeforces

Make Them Equal solution codeforces


Theofanis has a string 𝑠1𝑠2…𝑠𝑛s1s2…sn 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≀π‘₯≀𝑛1≀x≀n) and for every position 𝑖i, where 𝑖i is not divisible by π‘₯x, replace 𝑠𝑖si 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.

Make Them Equal solution codeforces

Input

The first line contains a single integer 𝑑t (1≀𝑑≀1041≀t≀104)Β β€” the number of test cases.

The first line of each test case contains the integer 𝑛n (3≀𝑛≀3β‹…1053≀n≀3β‹…105) 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β‹…1053β‹…105.

Make Them Equal solution codeforces

Output

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 π‘₯1,π‘₯2,…,π‘₯π‘šx1,x2,…,xm (1≀π‘₯𝑗≀𝑛1≀xj≀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.

Make Them Equal solution codeforces

 

Example

input

Copy
3
4 a
aaaa
4 a
baaa
4 b
bzyx

Make Them Equal solution codeforces

 

output

Copy
0
1
2
2 
2 3

Make Them Equal solution codeforces

Note

Let’s describe what happens in the third test case:

  1. π‘₯1=2x1=2: we choose all positions that are not divisible by 22 and replace them, i.Β e. bzyx β†’β†’ bzbx;
  2. π‘₯2=3x2=3: we choose all positions that are not divisible by 33 and replace them, i.Β e. bzbx β†’β†’ bbbb.

Make Them Equal solution codeforces


Make Them Equal solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment