Chef likes strings a lot but he likes palindromic strings even more. Today he found an old string s in his garage. The string is so old that some of its characters have faded and are unidentifiable now. Faded characters in the string are represented by '.' whereas other characters are lower case Latin alphabets i.e ['a'-'z'].

Chef being the palindrome lover decided to construct the lexicographically smallest palindrome by filling each of the faded character ('.') with a lower case Latin alphabet. Can you please help him completing the task?

-----Input-----
First line of input contains a single integer T denoting the number of test cases. T test cases follow.
First and the only line of each case contains string s denoting the old string that chef has found in his garage.

-----Output-----
For each test case, print lexicographically smallest palindrome after filling each faded character - if it possible to construct one. Print -1 otherwise.

-----Constraints-----
- 1 ≤ T ≤ 50
- 1 ≤ |s| ≤ 12345
- String s consists of ['a'-'z'] and '.' only.

-----Subtasks-----Subtask #1 (47 points)
- 1 ≤ T ≤ 50, 1 ≤ |S| ≤ 123
Subtask #2 (53 points)
- 1 ≤ T ≤ 50, 1 ≤ |S| ≤ 12345

-----Example-----Input
3
a.ba
cb.bc
a.b

Output
abba
cbabc
-1

-----Explanation-----
In example 1, you can create a palindrome by filling the faded character by 'b'.
In example 2, you can replace the faded character by any character from 'a' to 'z'. We fill it by 'a', as it will generate the lexicographically smallest palindrome.
In example 3, it is not possible to make the string s a palindrome.

Difficulty: interview

Starter code:

Solutions:
test=int(input())
for i in range(test):
    s=input()
    b=len(s)
    list1=[]
    for j in range(len(s)):
        if s[j]=='.':
            list1.append(j)
    for i in list1:
        if b-i-1 in list1 :
            if i!=b-i-1 and ((s[i] and s[b-i-1]) != 'a' ):
                s=s[:i]+'a'+s[i+1:b-i-1]+'a'+s[b-i:]
            else:
                s=s[:i]+'a'+s[i+1:]
        else:
            s=s[:i]+s[b-i-1]+s[i+1:]

    if s==s[::-1]:
        print(s)
    else:
        print(-1)

        

for _ in range(int(input())):
	s=list(input())
	n=len(s)
	f=0
	for i in range(n//2):
		if s[i]=='.' and s[n-i-1]=='.':
			s[i]='a'
			s[n-i-1]='a'
		elif s[i]=='.':
			s[i]=s[n-i-1]
		elif s[n-i-1]=='.':
			s[n-i-1]=s[i]
		else:
			if s[i]!=s[n-i-1]:
				f=1
				break
			else:
				continue
	if f:
		print('-1')
	else:
		if n%2:
			if s[n//2]=='.':
				s[n//2]='a'
		print(''.join(s))


import sys
import math
def main(arr):
    n=len(arr)-1 
    for i in range(len(arr)//2):
        a=arr[i]
        b=arr[n-i]
        if a!=b and a!="." and b!=".":
            return "-1"
        if a=="." and b==".":
            arr[i]="a"
            arr[n-i]="a"
        else:
            if a!=".":
                arr[n-i]=a 
            elif b!=".":
                arr[i]=b
    if arr[len(arr)//2]==".":
        arr[len(arr)//2]="a"
    return "".join(arr)
    
test=int(input())
for _ in range(test):
    arr=list(input())
    print(main(arr))
        


import sys
import math
def main(arr):
    n=len(arr)-1 
    for i in range(len(arr)//2):
        a=arr[i]
        b=arr[n-i]
        if a!=b and a!="." and b!=".":
            return "-1"
        if a=="." and b==".":
            arr[i]="a"
            arr[n-i]="a"
        else:
            if a!=".":
                arr[n-i]=a 
            elif b!=".":
                arr[i]=b
    if arr[len(arr)//2]==".":
        arr[len(arr)//2]="a"
    return "".join(arr)
    
test=int(input())
for _ in range(test):
    arr=list(input())
    print(main(arr))
    

import sys
import math

def main(arr):


    n=len(arr)-1 
    
    for i in range(len(arr)//2):
        
        a=arr[i]
        b=arr[n-i]
        if a!=b and a!="." and b!=".":
            return "-1"
        if a=="." and b==".":
            
            arr[i]="a"
            arr[n-i]="a"
        
        else:
            
            if a!=".":
                arr[n-i]=a 
            elif b!=".":
                arr[i]=b
        
    if arr[len(arr)//2]==".":
        arr[len(arr)//2]="a"
    return "".join(arr)

for _ in range(int(input())):
    arr=list(input())
    print(main(arr))
    

# cook your dish here
for i in range(int(input())):
    S=input()
    s=list(S)
    N=len(s)
    flag=True
    for i in range(N):
        if s[i]!=s[N-1-i] and s[i]!="." and s[N-1-i]!=".":
            flag=False
            print(-1)
            break
        elif s[i]=="." and s[N-1-i]==".":
            s[i]=s[N-1-i]="a"
        elif s[i]=="." and s[N-1-i]!=".":
            s[i]=s[N-1-i]
    
   
    
    if flag:
        p=""
        for i in s:
            p+=i
        print(p)

for u in range(int(input())):
    s=list(input())
    f=0
    n=len(s)
    i,j=0,n-1
    while(i<=j):
        if(s[i]=='.' and s[j]=='.'):
            s[i],s[j]='a','a'
            i+=1
            j-=1
        elif(s[i]=='.' or s[j]=='.'):
            if(s[i]=='.' and s[j]!='.'):
                s[i]=s[j]
            else:
                s[j]=s[i]
            i+=1
            j-=1
        elif(s[i]!='.' and s[j]!='.'):
            if(s[i]==s[j]):
                i+=1
                j-=1
            else:
                f=1
                break
    if(f==1):
        print(-1)
    else:
        print(''.join(s))


for t in range(int(input())):
    ss=input()
    result=None
    k=""
    s=list(ss)
    x=len(ss)-1
    if len(ss)==1:
        if ss=='.':
            ss='a'
        
    else:
        for i in range((len(s)//2)+1):
            if s[i]==s[x]:
                if s[i]=='.':
                    s[i]='a'
                    s[x]='a'
            elif s[i]=='.':
                z=s[x]
                s[i]=z
            elif s[x]=='.':
                y=s[i]
                s[x]=y
            else:
                result=-1
                break
            x=x-1
    if result==None:
        print(k.join(s))
    else:
        print(result)

# cook your dish here
t = int(input())

while t > 0:
    t -= 1
    s = list(input())
    res = True
    l = 0
    r = len(s)-1
    while l <= r:
        if s[l].isalpha() and s[r].isalpha():
            if s[l] != s[r]:
                res = False
                break
        elif s[l] == '.' and s[r] == '.':
            s[l] = 'a'
            s[r] = 'a'
        elif s[l] == '.':
            s[l] = s[r]
        else:
            s[r] = s[l]
        l += 1
        r -= 1
    if res:
        print("".join(s))
    else:
        print(-1)



t=int(input())
for h in range(t):
	s=list(input())
	n=len(s)
	f=0
	for i in range(n):
		if s[i]!='.' and s[i]!=s[n-i-1] and s[n-i-1]!='.':
			f=1
			print(-1)
			break
		elif s[i]=='.' and s[n-i-1]=='.':
			s[i]=s[n-i-1]='a'
		elif s[i]=='.' and s[n-i-1]!='.':
			s[i]=s[n-i-1]
	if f==0:
	    r=''
	    for i in s:
	        r=r+i
	    print(r)

for _ in range(int(input())):
	S=list(input())
	N=len(S)
	c=True
	for i in range(N):
		if S[i]!='.' and S[i]!=S[N-i-1] and S[N-i-1]!='.':
			c=False
			print('-1')
			break
		elif S[i]=='.' and S[N-i-1]=='.':
			S[i]=S[N-i-1]='a'
		elif S[i]=='.' and S[N-i-1]!='.':
			S[i]=S[N-i-1]
	if c:
	    p=''
	    for i in S:
	        p+=i
	    print(p)

# cook your dish here
for _ in range(int(input())):
    s = list(input())
    n = len(s)
    for i in range(n//2 + n%2):
        if s[i] == '.':
            if s[n-i-1] == '.': s[i], s[n-i-1] = 'a', 'a'
            else: s[i] = s[n-i-1]
        else:
            if s[n-i-1] == '.': s[n-i-1] = s[i]
            elif s[i] != s[n-i-1]:
                print(-1)
                break
    else:
        print(''.join(s))

for _ in range(int(input())):
	S=list(input())
	N=len(S)
	c=True
	for i in range(N):
		if S[i]!='.' and S[i]!=S[N-i-1] and S[N-i-1]!='.':
			c=False
			print('-1')
			break
		elif S[i]=='.' and S[N-i-1]=='.':
			S[i]=S[N-i-1]='a'
		elif S[i]=='.' and S[N-i-1]!='.':
			S[i]=S[N-i-1]
	if c:
	    p=''
	    for i in S:
	        p+=i
	    print(p)

for j in range(int(input())):
    a=input()
    x=list(a)
    n=len(x)
    am=0
    if(n%2==0):
        for i in range(n):
            if(x[i]=="." or x[n-i-1]=="."):
                if(x[i]=="." and x[n-i-1]!="."):
                    x[i]=x[n-i-1]
                elif(x[n-i-1]=="." and x[i]!="."):
                    x[n-i-1]=x[i]
                else:
                    x[i]="a"
                    x[n-i-1]="a"
            elif(x[i]!=x[n-i-1]):
                am=1
                break
    else:
        b=n//2
        for i in range(n):
            if(b==i):
                if(x[i]=="."):
                    x[i]="a"
                else:
                    continue
            elif(x[i] == "." or x[n - i - 1] == "."):
                if (x[i] == "." and x[n - i - 1] != "."):
                    x[i] = x[n - i - 1]
                elif (x[n - i - 1] == "." and x[i] != "."):
                    x[n - i - 1] = x[i]
                else:
                    x[i] = "a"
                    x[n - i - 1] = "a"
            elif(x[i]!=x[n-i-1]):
                am=1
                break
    if(am==0):
        print("".join(x))
    else:
        print(-1)

for _ in range(int(input())):
    s = list(input())
    start = 0
    end = len(s) - 1
    flag = True
    while start < end:
        if s[start] == '.' and s[end] != '.':
            s[start] = s[end]
        elif s[start] != '.' and s[end] == '.':
            s[end] = s[start]
        elif s[start] == '.' and s[end] == '.':
            s[start] = 'a'
            s[end] = 'a'
        elif s[start] == s[end]:
            start += 1
            end -= 1
        else:
            flag = False
            break

    if flag:
        if s[start] == '.':
            s[start] = 'a'
        print(''.join(x for x in s))
    else:
        print(-1)


# cook your dish here
t=int(input())
for i in range(t):
    s=list(input())
    
    for j in range(len(s)):
        
            if(s[j]=='.'):
                if(s[len(s)-j-1]=='.'):
                    s[j]=s[len(s)-j-1]='a'
                else:
                    s[j]=s[len(s)-j-1]
            elif(s[len(s)-j-1]=='.'):
                if(s[j]=='.'):
                    s[j]=s[len(s)-j-1]='a'
                else:
                    s[len(s)-j-1]=s[j]
            
            
            
                
            if(len(s)%2!=0):
                if(j==((len(s)//2))):
                
                    if(s[j]=='.'):
                        s[j]="a"
    c=""
    m=""
    flag=1
    c=list(c.join(s))
    for k in range(len(c)//2):
        if(c[k]==c[len(c)-k-1]):
            flag=0
            
            
        else:
            flag=1
            break
    if(flag==0):
        print(m.join(c))
    else:
        print(-1)
    
    

for _ in range(int(input())):
    str = list(input())
    l = len(str)
    flag = False
    for i in range(l//2):
        if str[i] == '.':
            if str[-i-1] == '.':
                str[i] = str[-i-1] = 'a'
            else:
                str[i] = str[-i-1]
        elif str[-i-1] == '.':
            str[-i-1] = str[i]
        elif str[i] != str[-i-1]:
            print("-1")
            flag = True
            break
    if flag:
        continue
    if l%2 != 0 and str[l//2] == '.':
        str[l//2] = 'a'
    print("".join(str))


for _ in range(int(input())):
	s = input()
	a, h, t = list(s), 0, len(s)-1
	flag = 0
	while h <= t:
		if a[h] != a[t] and (a[h] != "." and a[t] != '.'):
			flag = 1
			break
		elif a[h] == a[t] and a[h] == '.':
			a[h] = 'a'
			a[t] = a[h]
		elif a[h] != a[t]:
			if a[h] == '.':
				a[h] = a[t]
			elif a[t] == '.':
				a[t] = a[h]
		h += 1
		t -= 1
	y = ''.join(a)
	if flag == 0:
		print(y)
	else:
		print(-1)

t = int(input())
for q in range(t):
    s = input()
    ns = ''
    
    f = 0
    if len(s)%2 == 0:
        k = len(s) // 2
    else:
        k = (len(s)//2)+1
    
    for i in range(k):
    
        if s[i] != s[len(s)-1-i] and s[i] != '.' and s[len(s)-1-i] != '.':
            f = 1
            break
        elif s[i] == '.':
            if s[i] == s[len(s)-1-i]:
                ns += 'a'
            else:
                ns += s[len(s)-1-i]
        elif s[len(s)-1-i] == '.':
            if s[i] == s[len(s)-1-i]:
                ns += 'a'
            else:
                ns += s[i]
        else:
            ns += s[i]
    
    
    if f == 1:
        print(-1)
    elif len(s)%2 == 0:
        print(ns + ns[::-1])
    else:
        print(ns + ns[::-1][1:])

'''input
3
a.ba
c...c
...
'''
from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import  permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
from math import gcd
'''
Author : dhanyaabhirami
Hardwork beats talent if talent doesn't work hard
'''
'''
Stuck?
See github resources
Derive Formula
Kmcode blog
CP Algorithms Emaxx
'''
mod=pow(10,9) +7
def inp(flag=0):
    if flag==0:
        return list(map(int,input().strip().split(' ')))
    else:
        return int(input())

# Code credits
# assert(debug()==true)
# for _ in range(int(input())):

t=inp(1)
while t:
    t-=1
    
    s=input().strip()
    n=len(s)
    s=list(s)
    if n%2==1 and s[n//2]=='.':
    	s[n//2]='a'
    for i in range(n//2):
    	if s[i]==s[n-i-1]:
    		if s[i]=='.':
    			s[i]='a'
    			s[n-i-1]='a'
    		else:
    			continue
    	elif s[i]=='.':
    		s[i]=s[n-i-1]
    	elif s[n-i-1]=='.':
    		s[n-i-1]=s[i]
    	else:
    		s = -1
    		break
    if s!=-1:
    	s="".join(s)
    print(s)

# cook your dish here
t = int(input())
for q in range(t):
    s = input()
    ns = ''
    
    f = 0
    if len(s)%2 == 0:
        k = len(s) // 2
    else:
        k = (len(s)//2)+1
    
    for i in range(k):
    
        if s[i] != s[len(s)-1-i] and s[i] != '.' and s[len(s)-1-i] != '.':
            f = 1
            break
        elif s[i] == '.':
            if s[i] == s[len(s)-1-i]:
                ns += 'a'
            else:
                ns += s[len(s)-1-i]
        elif s[len(s)-1-i] == '.':
            if s[i] == s[len(s)-1-i]:
                ns += 'a'
            else:
                ns += s[i]
        else:
            ns += s[i]
    
    
    if f == 1:
        print(-1)
    elif len(s)%2 == 0:
        print(ns + ns[::-1])
    else:
        print(ns + ns[::-1][1:])


N = int(input())

for i in range(N):
    string = list(input())
    count = 0
    broken = False
    while count <= len(string) // 2:
        if string[count] == "." and string[-count - 1] == ".":
            string[-count - 1] = string[count] = "a"

        elif string[count] == ".":
            string[count] = string[-count - 1]

        elif string[-count - 1] == ".":
            string[-count - 1] = string[count]

        elif string[count] != string[-count - 1]:
            print(-1)
            broken = True
            break

        count += 1

    if not broken:
        print(''.join(string))


for _ in range(int(input())):
	s = input()
	a, h, t = list(s), 0, len(s)-1
	flag = 0
	while h <= t:
		if a[h] != a[t] and (a[h] != '.' and a[t] != '.'):
			flag = 1
			break
		elif a[h] == a[t] and a[h] == '.':
			a[h] = 'a'
			a[t] = a[h]
		elif a[h] != a[t]:
			if a[h] == '.':
				a[h] = a[t]
			elif a[t] == '.':
				a[t] = a[h]
		h += 1
		t -= 1
	s = ''.join(a)
	if flag == 0:
		print(s)
	else:
		print(-1)

# cook your dish here

t = int(input())
while(t!=0):
    word = input()
    split_word = list(word)
    flag = 0
    x = 0
    y = -1
    while(x<len(split_word)):
        if split_word[x]!='.' and split_word[y]!='.':
            if split_word[x]!=split_word[y]:
                flag =1
                break
        elif(split_word[x] == split_word[y] and split_word[x] == '.' and split_word[y] == '.'):
            split_word[x] = 'a'
            split_word[y] = 'a' 
        elif(split_word[x] == '.'): 
            split_word[x] = split_word[y]
        elif(split_word[y] == '.'): 
            split_word[y] = split_word[x]
        x += 1
        y -= 1
        
    if(flag == 1):
        print(-1)
    else:
        print(''.join(split_word))
    t = t-1
    



#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Nov  5 17:14:44 2019

@author: hkumar50
"""

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Nov  5 15:53:29 2019

@author: hkumar50
"""

def calres(x):
    l=len(x)
    x=list(x)
    flag=0
    #midcheck=0
    #nonmidVal=''
    
    if(l%2!=0):
        totItr=l//2+1
    else:
        totItr=l//2
    for i in range(0, totItr):
    
        if(  (x[i]=='.') or (x[(l-1)-i]  =='.') ):
            if( (len(x)%2!=0) and (i==len(x)//2) == (l-1-i) ):
                x[i]='a'
                #x[l-1-i]='a'
            elif( (x[i]=='.') and (x[l-1-i] != '.') ):
                x[i]=x[l-1-i]
                #midcheck=2
            elif( (x[i]!='.') and (x[l-1-i] == '.') ):
                x[l-1-i]=x[i]
                #midcheck=2
            elif((x[i]=='.') and (x[l-1-i] == '.')):
                x[i]='a'
                x[l-1-i]='a'
    
                
        elif( (x[i] == x[(l-1)-i])  ):
            flag=1
        else:
            flag=-1
            break
    
    
    if(flag==-1):
        print('-1')

    else:
        print( (''.join(x) ) )
        
        
t=int( input() )

for i in range(t):
    val=str(input())
    calres(val)