Avinash was given a row of stones. Each stone has one lowercase letter of the Latin alphabet written on it. The entire sequence of stones forms the string s.

In other words, you are given a string s consisting of lowercase Latin letters.

Initially, Avinash stands on the first stone of the row and wants to reach the last stone by jumping across the stones.

Jumping from the i-th stone to the j-th stone has a cost equal to:

|index(si) − index(sj)|

Here, index(c) is the position of the letter c in the alphabet:

• index('a') = 1
• index('b') = 2
• ...
• index('z') = 26

Avinash wants to reach the n-th stone with the minimum total cost, but among all such ways, he prefers the one with the maximum number of jumps.

He can visit each stone at most once.

Your task is to help Avinash — print the sequence of indices of stones on which he should jump.

• The first line contains an integer t — the number of test cases.
• Each test case consists of a string s — the sequence of stones.

The answer to each test case consists of single line.
Print two integers cost and m, where:

• cost — the minimum total cost of the path.
• m — the maximum number of stones visited to reach the last stone for the minimum total cost.