Permutation and Palindrome

You are given a string s with length n. You should find a permutation P of numbers 1 through n such that if you apply this permutation on the string s, you will get a palindromic string.

The result of applying a permutation P on the string s is a string t with length n such that for each i (1 ≤ i ≤ n), the i-th character of t is given as as t[i] = s[Pi].

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

• The first and only line of each test case contains the string s.

Output

For each test case, print a single line. If it is impossible to find a valid permutation P, this line should contain a single integer -1. Otherwise, it should contain n space-separated integers P1, P2, ..., Pn.

If there are multiple valid permutations, you may print any one.

Constraints

• 1 ≤ n ≤ 105

• s will consist only of lowercase English letters (i.e. characters 'a' through 'z')

Subtasks

Subtask #1 (20 points): 1 ≤ T, n ≤ 10

Subtask #2 (20 points): 1 ≤ T, n ≤ 100

Subtask #3 (60 points): 1 ≤ T ≤ 10

Example

Input

4
aa
baa
abc
abab

Output

1 2
2 1 3
-1
1 2 4 3

Explanation

Example case 1: The string t obtained using the identity permutation will have t[1] = s[1] and t[2] = s[2]. That means t = "aa", which is a palindrome.

Example case 2: The characters of the string t obtained by applying the permutation 2, 1, 3 are t[1] = s[2], t[2] = s[1] and t[3] = s[3]. Therefore, t = "aba", which is a palindrome.

Example case 3: There is no way to find a permutation P such that we can obtain a palindrome from s using it.

Example case 4: Applying the permutation 1, 2, 4, 3 on s results in t = "abba", which is a palindrome. Another permutation that you may apply is 2, 1, 3, 4; this results in t = "baab", which is also a palindrome.

class Codechef {
    public static int[] createPalindrome(String str) {
        // Map of char -> indices
        Map<Character, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++)
            map.computeIfAbsent(str.charAt(i), k -> new ArrayList<>()).add(i);

        int oddCount = 0;
        for (char c : map.keySet())
            if (map.get(c).size() % 2 != 0)
                oddCount++;
        // If there are more than 1 chars with odd freq
        if (oddCount > 1)
            return new int[] { -1 };
        int[] ans = new int[str.length()];
        int start = 0, end = str.length() - 1;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int zeroOrOne = map.get(c).size() % 2;
            while (map.get(c).size() > zeroOrOne) {
                // Taking indices from end of list
                ans[start++] = map.get(c).get(map.get(c).size() - 1) + 1;
                map.get(c).remove(map.get(c).size() - 1);
                ans[end--] = map.get(c).get(map.get(c).size() - 1) + 1;
                map.get(c).remove(map.get(c).size() - 1);
            }
            if (map.get(c).size() == 1) {
                // Putting odd count char in between
                ans[(start + end) / 2] = map.get(c).get(0) + 1;
                map.get(c).remove(0);
            }
        }
        return ans;
    }
}