Jotformers throw a party to celebrate their new office in METU. Faruk, the bartender at this party, while brewing drinks, realizes that it will be impossible to serve all Jotformers in the queue in order before the party ends. Faruk also realizes that Jotformers from the same team \(s_i\) (he understands from their badges) always get the same drink. Since he can make the same type of drink sequentially very quickly, he comes up with an idea.

The idea is to serve drinks of the same type first and then switch to drinks with the least different materials to lessen the amount of time for switching. Hence serving a maximum number of drinks with a minimum amount of total time. He also doesn't want to wait the first person in the queue and the last person in the queue too much, so the service will start with the first person and end with the last person in the queue. He will skip people in between, if he will serve the drinks faster. However, he doesn't have the time to figure out the solution, so he calls you!

He quickly scans the queue and tells you the teams in the queue with a string \(s\). The string \(s\) consists of the first letters of the Jotformers' teams in the queue. Faruk also tells you that:

1. He can instantly brew the same type of drink if it is the same type of drink he brewed before.
2. When switching from one type of drink to another, he will spend minutes equal to the absolute of the difference between the team's first letter's position in the alphabet. E.g. \(s_i=a\) and \(s_j=c\), so the amount of time he will spend while switching equals to \(\left | 1 - 3 \right | = 2\) minutes.

Your job is to find the order Faruk should serve the Jotformers in the queue, ensuring a maximum number of drinks in the shortest amount of time.

Input

• First line of the input will be the amount of test cases \(t\)
• The first line of each test case will be the length of the string \(n\).
• The second line of each test case will be the string \(s\). \(s\) will only consist of lowercase ASCII alphabet characters.
• \(1 \leq t \leq 10^{4}\)
• \(1 \leq n \leq 10^{4}\)

Output

For each test case, the first line will be the minimum amount of minutes \(m\) Faruk will spend to serve. The second line will be the indexes \(i\) of \(s\) that Faruk served in order.

Example

Input

3
5
egfdh
12
aabbccaabbcc
12
jotformrocks

Output

3
1 3 2 5
2
1 2 7 8 3 4 9 10 5 6 11 12
9
1 11 7 2 5 9 6 8 12

 Explanation

For the first case the values are as follows val('e')=5, val('f')=6, val('g')=7,val('d')=4, val('h')=8. Since the first Jotformer's team is e, Faruk will first jump to f, then g and h.

There are total of 3 switches. \(\left| val(\textrm{'e'}) - val(\textrm{'f'}) \right| + \left| val(\textrm{'f'}) - val(\textrm{'g'}) \right| + \left| val(\textrm{'g'}) - val(\textrm{'h'}) \right| = 3\)