import java.util.Set;
import java.util.TreeSet;

public class Palindrome{

 static int loop =0;

   public static boolean checkPalindrome(String word){

     int length = word.length();

     if(length ==0 && loop ==0){
       loop =0;
       return false;
     }
     loop++;

         if((length == 1 || length ==0 ) && loop > 0)
              return true;
         else{
             if(word.charAt(0) == word.charAt(length-1) )
                 return checkPalindrome(word.substring(1,length-1));
             loop =0;
             return false;
         }
     }

   public static Set<String> permute(String chars)
   {

     Set<String> set = new TreeSet<String>();

     if (chars.length() == 1)
     {
       set.add(chars);
     }
     else
     {

       for (int i=0; i<chars.length(); i++)
       {

         String pre = chars.substring(0, i);
         String post = chars.substring(i+1);
         String remaining = pre+post;


         for (String permutation : permute(remaining))
         {

           set.add(chars.charAt(i) + permutation);
         }
       }
     }
     return set;
   }

   public static void compute_palindromes(String[] s){
    int i;
    for (i=0;i<s.length;i++){
    boolean check =false;
    for (String str : Palindrome.permute(s[i])){

     check =  checkPalindrome(str);
     if(check == true){
      System.out.println(s[i]+":"+str);
      break;
     }


         }
    if(check ==false){
     System.out.println(s[i]+":1");
    }

  }

   }

   public static void main(String[] args){
    String[] words = {"ivcci","oyotta","bbb","babbb"};
    compute_palindromes(words);
    }
}