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’)

Input

4

aa

baa

abc

abab

Output

1 2

2 1 3

-1

1 2 4 3

i have tried my hands on this problem but i could not pass any of the test case . My solution :

   #include<bits/stdc++.h>     using namespace std;      template <class T>     void printVect(vector<T> v){     long long  i;     for(i=0;i<v.size()-1;i++)     {         cout<<v[i]<<" ";     }     cout<<v[i]<<endl;     }      int main(){     int t;     cin>>t;     string s;     long long n;     long long l,r;     while(t--)     {         map<char,int> umap;         cin>>s;         n=s.size();         vector<int > soln(n,0);         l=1;r=n;         for(long long  i=0;i<n;i++)         {              if(umap.find(s[i])!=umap.end())             {                 soln[umap[s[i]]]=l;                 soln[i]=r;                 l++;r--;                 //cout<<s[i]<<" "<<l<<" "<<r<<endl;                // printVect(soln);                 umap.erase(s[i]);             }             else{                 umap[s[i]]=i;              }         }         if(umap.size()==1){             soln[umap.begin()->second]=l;             umap.erase(umap.begin()->first);          }         if(umap.size()==0){             printVect(soln);          }         else             cout<<-1<<endl;       }      } 

here am inserting each new element to the map with key equal to the initial position and after a match is found am placing it on the mirror position .If it has odd elements then the final element is placed at the middle . After all these operations if there is still non zero elements then this is not a palindrome