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: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	s1 = input()
	s2 = s1[::-1]
	f = 0
	for i in range(len(s1)):
		if s1[i] == '.' and s2[i] != '.':
			s1 = s1.replace(s1[i], s2[i], 1)
		if s1[i] == '.' and s2[i] == '.':
			s1 = s1.replace(s1[i], 'a', 1)
		if s1[i].isalpha() and s2[i].isalpha() and (s1[i] != s2[i]):
			print(-1)
			f = 1
			break
	if f == 0:
		print(s1)


n = int(input())
for i in range(n):
	b = list(input())
	a = ''
	for i in range(len(b)):
		if b[i] == '.':
			if b[i] == b[len(b) - i - 1]:
				b[i] = 'a'
			else:
				b[i] = b[len(b) - i - 1]
	if b == b[::-1]:
		for j in b:
			a = a + str(j)
		print(a)
	else:
		print(-1)


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'
		elif 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))


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


t = int(input())
for ni in range(t):
	s = input()
	s = list(s)
	n = len(s)
	for i in range(n):
		if s[i] == '.':
			if s[n - i - 1] == '.':
				s[i] = 'a'
				s[n - i - 1] = 'a'
			else:
				s[i] = s[n - i - 1]
	s = ''.join(s)
	if s == s[::-1]:
		print(s)
	else:
		print(-1)


t = input()
for c in range(0, int(t)):
	s = [x for x in input()]
	n = len(s)
	for i in range(n):
		if i == n // 2 and n % 2 == 1 and (s[i] == '.'):
			s[i] = 'a'
		elif s[i] == '.' and s[n - i - 1] == '.':
			s[i] = 'a'
			s[n - i - 1] = 'a'
		elif s[i] == '.':
			s[i] = s[n - i - 1]
	flag = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			flag = 1
			break
	print(''.join(s) if flag == 0 else -1)


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for i in range(ii()):
	s = ip()
	i = 0
	j = len(s) - 1
	st1 = ''
	st2 = ''
	f = True
	while i <= j:
		if i == j:
			if s[i] == '.':
				st1 += 'a'
				break
			else:
				st1 += s[i]
				break
		if s[i] == '.' and s[j] != '.':
			st1 += s[j]
			st2 += s[j]
		if s[j] == '.' and s[i] != '.':
			st2 += s[i]
			st1 += s[i]
		if s[i] == '.' and s[j] == '.':
			st1 += 'a'
			st2 += 'a'
		if s[i] != '.' and s[j] != '.':
			if s[i] == s[j]:
				st1 += s[i]
				st2 += s[j]
			else:
				f = False
				print(-1)
				break
		i += 1
		j -= 1
	if f:
		print(st1 + st2[::-1])


t = int(input())
for _ in range(t):
	s = input()
	test = True
	index = 0
	l = [i for i in s]
	if len(s) % 2 == 0:
		index = len(s) // 2
	else:
		index = len(s) // 2 + 1
		if l[len(s) // 2] == '.':
			l[len(s) // 2] = 'a'
	for i in range(index, len(s)):
		if l[i] == '.' and l[-i - 1] != '.':
			l[i] = l[-i - 1]
		elif l[i] != '.' and l[-i - 1] == '.':
			l[-i - 1] = l[i]
		elif l[i] == '.' and l[-i - 1] == '.':
			l[-i - 1] = 'a'
			l[i] = 'a'
		elif l[i] != l[-i - 1]:
			test = False
			break
	if test:
		print(''.join(l))
	else:
		print(-1)


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


for _ in range(int(input())):
	s1 = input()
	n = len(s1)
	s2 = ''
	for i in range(n):
		if s1[i] != '.' and s1[n - i - 1] != '.' and (s1[i] != s1[n - i - 1]):
			s2 = '-1'
			break
		if s1[i] == '.':
			if s1[n - i - 1] != '.':
				s2 += s1[n - i - 1]
			else:
				s2 += 'a'
		else:
			s2 += s1[i]
	print(s2)


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 _ in range(int(input())):
	s = input()
	while '.' in s:
		a = s.index('.')
		s = s[:a] + s[len(s) - a - 1] + s[a + 1:]
		if a == len(s) - a - 1 or s[len(s) - a - 1] == '.':
			s = s[:a] + 'a' + s[a + 1:]
	if s[::-1] == s:
		print(s)
	else:
		print(-1)


t = int(input())
for tc in range(t):
	x = input()
	a = len(x)
	X = list(x)
	for i in range(a // 2):
		if X[i] == '.' and X[a - i - 1] == '.':
			X[i] = 'a'
			X[a - i - 1] = 'a'
		elif X[i] == '.' and X[a - i - 1] != '.':
			X[i] = X[a - i - 1]
		elif X[i] != '.' and X[a - i - 1] == '.':
			X[a - i - 1] = X[i]
	if a % 2 == 1:
		if X[a // 2] == '.':
			X[a // 2] = 'a'
	new = ''.join(map(str, X))
	rev = ''
	for i in range(a):
		rev += new[a - i - 1]
	if rev == new:
		print(new)
	else:
		print(-1)


for _ in range(int(input())):
	s = input()
	ans = ''
	for i in range(len(s)):
		if s[i] == s[-i - 1]:
			if s[i] == '.':
				ans += 'a'
			else:
				ans += s[i]
		elif s[i] == '.':
			ans += s[-i - 1]
		elif s[-i - 1] == '.':
			ans += s[i]
		else:
			ans = -1
			break
	print(ans)


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()
	s1 = s[::-1]
	x = ''
	for i in range(len(s)):
		if s[i] == '.' and s1[i] != '.':
			x += s1[i]
		elif s[i] == '.':
			x += 'a'
		else:
			x += s[i]
	if x == x[::-1]:
		print(x)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	L = list(input())
	n = len(L)
	found = False
	for i in range(n):
		if L[i] == '.':
			if L[n - 1 - i] != '.':
				L[i] = L[n - 1 - i]
			else:
				L[n - 1 - i] = 'a'
				L[i] = 'a'
		elif L[n - i - 1] == '.':
			L[n - i - 1] = L[i]
		elif L[n - i - 1] == L[i]:
			pass
		else:
			found = True
			break
	if found:
		print(-1)
	else:
		print(''.join(L))


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)


try:
	t = int(input())
	i = 1
	while i <= t:
		i = i + 1
		a = input()
		lst1 = []
		lst2 = []
		lst3 = []
		for z in a:
			lst1.append(z)
		n = len(lst1)
		not_pal = 0
		if n == 1:
			if lst1[0] == '.':
				print('a')
			else:
				print(lst1[0])
		elif n % 2 == 0:
			for c in range(0, n // 2):
				lst2.append(lst1[c])
			for v in range(n - 1, n // 2 - 1, -1):
				lst3.append(lst1[v])
			for k in range(0, len(lst2)):
				if lst2[k] != lst3[k]:
					if lst2[k] == '.':
						lst2[k] = lst3[k]
					elif lst3[k] == '.':
						lst3[k] = lst2[k]
					else:
						not_pal = -1
				elif lst2[k] == '.' and lst3[k] == '.':
					lst2[k] = 'a'
					lst3[k] = 'a'
			if not_pal == -1:
				print(-1)
			else:
				print(''.join(lst2) + ''.join(lst3)[len(lst3) - 1::-1])
		else:
			for c in range(0, n // 2):
				lst2.append(lst1[c])
			for v in range(n - 1, n // 2, -1):
				lst3.append(lst1[v])
			for k in range(0, len(lst2)):
				if lst2[k] != lst3[k]:
					if lst2[k] == '.':
						lst2[k] = lst3[k]
					elif lst3[k] == '.':
						lst3[k] = lst2[k]
					else:
						not_pal = -1
				elif lst2[k] == '.' and lst3[k] == '.':
					lst2[k] = 'a'
					lst3[k] = 'a'
			if lst1[n // 2] == '.':
				lst1[n // 2] = 'a'
			if not_pal == -1:
				print(-1)
			else:
				print(''.join(lst2) + lst1[n // 2] + ''.join(lst3)[len(lst3) - 1::-1])
except:
	pass


try:
	n = int(input())
	for i in range(n):
		flag = ''
		s = str(input())
		s = list(s)
		j = -1
		for i in range(0, len(s)):
			if s[i] != s[j] and s[i] == '.':
				s[i] = s[j]
			if s[i] != s[j] and s[j] == '.':
				s[j] = s[i]
			if s[i] != s[j]:
				flag = 'fail'
				break
			if s[i] == s[j] == '.':
				s[i] = 'a'
				s[j] = 'a'
			j = j - 1
		if flag == 'fail':
			print(-1)
			continue
		string = ''
		for i in s:
			string = string + i
		print(string)
except EOFError:
	pass


for _ in range(int(input())):
	in_str = list(input())
	ll = len(in_str)
	ans = 0
	if ll % 2:
		ll_rng = int(ll // 2 + 1)
	else:
		ll_rng = int(ll / 2)
	for i in range(ll_rng):
		if in_str[i] != in_str[ll - i - 1]:
			if in_str[i] == '.':
				in_str[i] = in_str[ll - i - 1]
			elif in_str[ll - i - 1] == '.':
				in_str[ll - i - 1] = in_str[i]
			else:
				ans = '-1'
				break
		elif in_str[i] == '.' and in_str[ll - i - 1] == '.':
			in_str[i] = in_str[ll - i - 1] = 'a'
	if ans == '-1':
		print(ans)
	else:
		print(''.join(in_str))


import sys
import bisect
import numpy as np
input = sys.stdin.readline
r = int(input().strip())
for _ in range(r):
	x = str(input().strip())
	flag = True
	ans = ''
	ans2 = ''
	if len(x) % 2 == 0:
		for i in range(len(x) // 2):
			j = i * -1 - 1
			if x[i] == x[j]:
				if x[i] == '.':
					ans += 'a'
				else:
					ans += x[i]
			elif x[i] == '.':
				ans += x[j]
			elif x[j] == '.':
				ans += x[i]
			else:
				flag = False
				break
		if flag:
			for i in range(len(ans)):
				j = i * -1 - 1
				ans2 += ans[j]
			ans += ans2
		else:
			ans = -1
	else:
		for i in range(len(x) // 2):
			j = i * -1 - 1
			if x[i] == x[j]:
				if x[i] == '.':
					ans += 'a'
				else:
					ans += x[i]
			elif x[i] == '.':
				ans += x[j]
			elif x[j] == '.':
				ans += x[i]
			else:
				flag = False
				break
		if flag:
			for i in range(len(ans)):
				j = i * -1 - 1
				ans2 += ans[j]
			if x[len(x) // 2] == '.':
				ans = ans + 'a' + ans2
			else:
				ans = ans + x[len(x) // 2] + ans2
		else:
			ans = -1
	print(ans)


t = int(input())
for i in range(t):
	l = list(input())
	k = 0
	s = l[::-1]
	for j in range(len(l)):
		if l[j] == '.':
			l[j] = s[j]
		if s[j] == '.':
			s[j] = l[j]
		if l[j] == s[j] == '.':
			s[j] = 'a'
			l[j] = 'a'
		if l[j] != s[j]:
			print(-1)
			k = -1
			break
	if k != -1:
		print(''.join(l))


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


T = int(input())
ans = []
for _ in range(T):
	S = input()
	s = ''
	N = len(S)
	for i in range(N):
		if S[i] != '.' and S[N - i - 1] != '.' and (S[i] != S[N - i - 1]):
			s = -1
			break
		elif S[i] == '.' and S[N - i - 1] == '.':
			s += 'a'
		elif S[i] == '.' and S[N - i - 1] != '.':
			s += S[N - i - 1]
		else:
			s += S[i]
	ans.append(s)
for i in ans:
	print(i)


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)


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


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 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())):
	s = list(input())
	l = s[::-1]
	t = 0
	for i in range(len(s)):
		if s[i] == '.':
			s[i] = l[i]
		if l[i] == '.':
			l[i] = s[i]
		if l[i] == s[i] == '.':
			s[i] = chr(97 + t)
			l[i] = chr(97 + t)
		if s[i] != l[i]:
			print(-1)
			t = -1
			break
	if t != -1:
		print(''.join(s))


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


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:])


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 x in range(int(input())):
	s = input()
	a = list(s)
	ra = a[::-1]
	n = len(s)
	for i in range(n):
		if a[i] == '.':
			a[i] = a[n - i - 1]
	ra = a[:]
	ra.reverse()
	if a == ra:
		for i in range(n):
			if a[i] == '.':
				a[i] = 'a'
		print(''.join((str(i) for i in a)))
	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)


for _ in range(int(input())):
	s = list(input())
	n = len(s)
	for i in range(n):
		if s[i] == '.':
			if s[i] == s[n - 1 - i]:
				s[i] = 'a'
			else:
				s[i] = s[n - 1 - i]
	if s == s[::-1]:
		print(''.join(map(str, s)))
	else:
		print(-1)


for _ in range(int(input())):
	s = input()
	i = 0
	j = len(s) - 1
	flag = True
	one = ''
	two = ''
	while i <= j:
		if s[i] == '.' and s[j] == '.':
			if i == j:
				one += 'a'
			else:
				one += 'a'
				two = 'a' + two
		elif s[i] == '.' and s[j] != '.':
			one += s[j]
			two = s[j] + two
		elif s[i] != '.' and s[j] == '.':
			one += s[i]
			two = s[i] + two
		elif s[i] == s[j]:
			if i == j:
				one += s[i]
			else:
				one += s[i]
				two = s[j] + two
		elif s[i] != s[j]:
			flag = False
			break
		i += 1
		j -= 1
	if flag:
		print(one + two)
	else:
		print('-1')


for i in range(int(input())):
	st = list(input())
	a = len(st)
	s = 0
	l = a - 1
	wine = 1
	while s < a + 1 // 2:
		if st[s] == '.' or st[l] == '.':
			if st[s] == '.' and st[l] == '.':
				st[s] = 'a'
				st[l] = 'a'
			elif st[s] == '.':
				st[s] = st[l]
			else:
				st[l] = st[s]
		elif st[s] != st[l]:
			wine = 0
			break
		s += 1
		l -= 1
	ans = ''
	if wine == 1:
		for z in st:
			ans += z
		print(ans)
	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)


tc = int(input())
for _ in range(tc):
	arr = list(input())
	low = 0
	high = len(arr) - 1
	while low <= high:
		if low == high and arr[low] == '.':
			arr[low] = 'a'
		elif arr[low] == arr[high] and arr[low] != '.':
			pass
		elif arr[low] == '.' and arr[high] == '.':
			arr[low] = 'a'
			arr[high] = 'a'
		elif arr[low] == '.':
			arr[low] = arr[high]
		elif arr[high] == '.':
			arr[high] = arr[low]
		else:
			print(-1)
			break
		low += 1
		high -= 1
	if low > high:
		print(''.join((i for i in arr)))


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)


n = int(input())
for _ in range(n):
	s = input()
	l = list(s)
	flag = True
	for i in range(len(s)):
		if l[i] == '.':
			if l[i] == l[-i - 1]:
				(l[i], l[-1 - i]) = ('a', 'a')
				continue
			else:
				l[i] = l[-i - 1]
		elif l[-1 - i] == '.':
			if l[i] == l[-i - 1]:
				(l[i], l[-1 - i]) = ('a', 'a')
				continue
			else:
				l[-i - 1] = l[i]
		elif l[i] != l[-i - 1]:
			flag = False
			break
	if flag:
		for i in l:
			print(i, end='')
		print()
	else:
		print(-1)


for tc in range(int(input())):
	st = input()
	s = list(st)
	n = len(s)
	for i in range(n):
		if s[i] == '.':
			if s[n - i - 1] == '.':
				s[n - i - 1] = 'a'
				s[i] = 'a'
			else:
				s[i] = s[n - i - 1]
	if s == s[::-1]:
		print(*s, sep='')
	else:
		print(-1)


for _ in range(int(input())):
	l = list(input())
	a = ''
	for i in range(len(l)):
		if l[i] == '.':
			if l[i] == l[len(l) - 1 - i]:
				l[i] = 'a'
			else:
				l[i] = l[len(l) - 1 - i]
	if l == l[::-1]:
		for j in l:
			a = a + str(j)
		print(a)
	else:
		print(-1)


a = int(input(''))
for i in range(a):
	t = input('')
	t1 = t[::-1]
	x = ''
	for j in range(len(t)):
		if t[j] == '.' and t1[j] != '.':
			x += t1[j]
		elif t[j] == '.':
			x += 'a'
		else:
			x += t[j]
	if x == x[::-1]:
		print(x)
	else:
		print(-1)


def calres(x):
	l = len(x)
	x = list(x)
	flag = 0
	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'
			elif x[i] == '.' and x[l - 1 - i] != '.':
				x[i] = x[l - 1 - i]
			elif x[i] != '.' and x[l - 1 - i] == '.':
				x[l - 1 - i] = x[i]
			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)


def anss(s):
	n = len(s)
	s = list(s)
	ans = ''
	if n % 2 != 0 and s[n // 2] == '.':
		s[n // 2] = 'a'
	for i in range(n // 2):
		if s[i] == s[n - i - 1] or s[i] == '.' or s[n - i - 1] == '.':
			if s[i] == '.' and s[n - i - 1] != '.':
				s[i] = s[n - i - 1]
			elif s[i] != '.' and s[n - i - 1] == '.':
				s[n - i - 1] = s[i]
			elif s[i] == '.' and s[n - i - 1] == '.':
				s[i] = 'a'
				s[n - i - 1] = 'a'
		else:
			return -1
			break
	if len(s) > 0:
		for i in s:
			ans += i
		return ans
for _ in range(int(input())):
	s = input()
	print(anss(s))


def pal(s):
	s = list(s)
	i = 0
	j = len(s) - 1
	while i <= j:
		if s[i] == '.' and s[j] != '.':
			s[i] = s[j]
		elif s[i] != '.' and s[j] == '.':
			s[j] = s[i]
		elif i == j and s[i] == '.':
			s[i] = 'a'
		elif s[i] == '.' and s[j] == '.':
			s[i] = 'a'
			s[j] = 'a'
		elif s[i] != s[j]:
			return -1
		i += 1
		j -= 1
	return ''.join(s)
for _ in range(int(input())):
	s = input()
	print(pal(s))


t = int(input())
for _ in range(t):
	str = list(input())
	length = len(str)
	flag = 0
	if length % 2 == 1 and str[length // 2] == '.':
		str[length // 2] = 'a'
	for i in range(length // 2):
		if str[i] != str[-(i + 1)]:
			if str[i] == '.' or str[-(i + 1)] == '.':
				if str[i] == '.' and str[-(i + 1)] != '.':
					str[i] = str[-(i + 1)]
				elif str[-(i + 1)] == '.' and str[i] != '.':
					str[-(i + 1)] = str[i]
			else:
				flag = 1
				break
		elif str[i] == '.' and str[-(i + 1)] == '.':
			str[i] = str[-(i + 1)] = 'a'
	if flag > 0:
		print(-1)
	else:
		str = ''.join(str)
		print(str)


t = int(input(''))
for _ in range(t):
	st = input('')
	flag = 0
	s = []
	for i in range(len(st)):
		s.append(st[i])
	n = len(s)
	if 1 <= n <= 12345 and (st.islower() or st == n * '.'):
		for i in range((n + 1) // 2):
			if s[i] == s[n - i - 1] and s[i] != '.' and (s[n - i - 1] != '.'):
				continue
			elif s[i] == '.' and s[n - i - 1] == '.':
				s[i] = 'a'
				s[n - i - 1] = 'a'
			elif s[n - i - 1] == '.':
				s[n - i - 1] = s[i]
			elif s[i] == '.':
				s[i] = s[n - i - 1]
			else:
				print(-1)
				flag = 1
				break
		if flag == 0:
			for i in s:
				print(i, end='')
			print()


tests = int(input())
for i in range(tests):
	string = input()
	length = len(string)
	ans = [0] * length
	palindrome = True
	if length & 1:
		end = length // 2 + 1
	else:
		end = length // 2
	for j in range(end):
		if string[j] == '.':
			if string[-(j + 1)] != '.':
				ans[j] = string[-(j + 1)]
				ans[-(j + 1)] = string[-(j + 1)]
			else:
				ans[j] = 'a'
				ans[-(j + 1)] = 'a'
		elif string[-(j + 1)] == '.' or string[j] == string[-(j + 1)]:
			ans[j] = string[j]
			ans[-(j + 1)] = string[j]
		else:
			palindrome = False
			break
	if not palindrome:
		print(-1)
	else:
		print(''.join(ans))


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
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return 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)


for t in range(int(input())):
	s = input()
	n = len(s)
	ans = list(s)
	for i in range(n):
		if ans[i] == '.':
			ans[i] = ans[n - 1 - i]
	ans2 = ans[:]
	ans2.reverse()
	if ans == ans2:
		for i in range(n):
			if ans[i] == '.':
				ans[i] = 'a'
		print(''.join((str(i) for i in ans)))
	else:
		print(-1)


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


def even(s1, s2):
	for x in range(0, int(a / 2)):
		if s1[x] == '.' and s2[x] != '.':
			s1[x] = s2[x]
		elif s1[x] != '.' and s2[x] == '.':
			s2[x] = s1[x]
		elif s1[x] == '.' and s2[x] == '.':
			s2[x] = 'a'
			s1[x] = 'a'
		elif s1[x] != s2[x]:
			print(-1)
			return
	if s2[-1] == '.':
		s2[-1] = 'a'
	print(''.join(s1) + ''.join(s2)[::-1])
for oo in range(int(input())):
	s = input()
	a = len(s)
	if a % 2 == 0:
		s1 = s[:int(a / 2)]
		s2 = s[int(a / 2):][::-1]
		s1 = list(s1)
		s2 = list(s2)
		even(s1, s2)
	else:
		s1 = s[:int(a / 2)]
		s2 = s[int(a / 2):][::-1]
		s1 = list(s1)
		s2 = list(s2)
		even(s1, s2)


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)


T = int(input())
for _ in range(T):
	A = [str for str in input()]
	N = len(A)
	for i in range(N):
		if A[i] == '.':
			if A[i] == A[N - i - 1]:
				A[i] = 'a'
			else:
				A[i] = A[N - i - 1]
	if A == A[::-1]:
		print(*A, sep='')
	else:
		print(-1)


for oo in range(int(input())):
	l = input()
	flag = 0
	c = 0
	z = 'a'
	n = list(l)
	k = len(n)
	for j in range(0, k // 2):
		if n[j] == '.' and n[k - j - 1] == '.':
			n[j] = n[k - j - 1] = 'a'
		elif n[j] != n[k - j - 1]:
			if n[j] == '.':
				n[j] = n[k - j - 1]
			elif n[k - j - 1] == '.':
				n[k - j - 1] = n[j]
			else:
				flag = 1
				break
	if k % 2 == 1 and n[k // 2] == '.' and (flag == 0):
		n[k // 2] = z
	if flag == 1:
		print('-1')
	else:
		print(''.join(n))


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)


t = int(input())
while t:
	s = [ch for ch in input()]
	n = len(s)
	found = True
	for i in range(n):
		if s[i] == '.' and s[n - 1 - i] == '.':
			s[i] = s[n - 1 - i] = 'a'
		elif s[i] == '.':
			s[i] = s[n - 1 - i]
		elif s[n - i - 1] == '.':
			s[n - 1 - i] = s[i]
		elif s[i] != s[n - i - 1]:
			found = False
	if found:
		ans = ''.join(s)
		print(ans)
	else:
		print(-1)
	t -= 1


for _ in range(int(input())):
	s = list(input())
	n = len(s)
	flag = False
	mid = n // 2
	if n % 2 == 0:
		L = s[:mid]
		R = s[mid:]
		R = R[::-1]
	else:
		L = s[:mid]
		R = s[mid + 1:]
		R = R[::-1]
	for i in range(mid):
		if L[i] == '.' and R[i] == '.':
			L[i] = 'a'
			R[i] = 'a'
		elif L[i] == '.':
			L[i] = R[i]
		elif R[i] == '.':
			R[i] = L[i]
		elif L[i] == R[i]:
			continue
		elif L[i] != R[i]:
			flag = True
			break
	R = R[::-1]
	if n % 2 == 0:
		p = L + R
		if flag:
			print(-1)
		else:
			ans = ''
			for i in p:
				ans += i
			print(ans)
	else:
		if s[mid] == '.':
			s[mid] = 'a'
		p = L + [s[mid]] + R
		if flag:
			print(-1)
		else:
			ans = ''
			for i in p:
				ans += i
			print(ans)


for tc in range(int(input())):
	s = input()
	l = len(s) - 1
	for i in range(len(s) // 2):
		if s[i] == '.' or s[l - i] == '.':
			if s[i] == '.' and s[l - i] == '.':
				prev = s
				s = s[0:i] + 'a' + s[i + 1:l - i] + 'a'
				if i != 0:
					s += prev[l - i + 1:]
			elif s[i] == '.':
				s = s[0:i] + s[l - i] + s[i + 1:]
			elif s[l - i] == '.':
				prev = s
				s = s[0:l - i] + s[i]
				if i != 0:
					s += prev[l - i + 1:]
	if (l + 1) % 2 == 1 and s[len(s) // 2] == '.':
		s = s[:len(s) // 2] + 'a' + s[len(s) // 2 + 1:]
	if s == s[::-1]:
		print(s)
	else:
		print(-1)


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


for _ in range(int(input())):
	s = input()
	(l1, l2) = ([], [])
	(flag, n) = (0, len(s))
	for i in range(n - (n & 1) >> 1):
		if s[i] == s[n - 1 - i]:
			if s[i] == '.':
				l1.append('a')
				l2.append('a')
			else:
				l1.append(s[i])
				l2.append(s[n - 1 - i])
		elif s[i] == '.':
			l1.append(s[n - 1 - i])
			l2.append(s[n - 1 - i])
		elif s[n - 1 - i] == '.':
			l1.append(s[i])
			l2.append(s[i])
		else:
			flag = 1
			break
	if flag == 1:
		print(-1)
	else:
		if n % 2 == 0:
			for i in l1 + l2[::-1]:
				print(i, end='')
		elif s[n >> 1] == '.':
			for i in l1 + ['a'] + l2[::-1]:
				print(i, end='')
		else:
			for i in l1 + [s[n >> 1]] + l2[::-1]:
				print(i, end='')
		print()


t = int(input())
for _ in range(0, t):
	s = input()
	l = list(s)
	n = len(l)
	t = 0
	for i in range(0, (n + 1) // 2):
		a = l[i]
		b = l[-(i + 1)]
		if a != b:
			if a != '.' and b != '.':
				print(-1)
				t = 1
				break
			elif a == '.' and b != '.':
				l[i] = b
			elif a != '.' and b == '.':
				l[-(i + 1)] = a
		elif a == '.' and b == '.':
			l[i] = 'a'
			l[-(i + 1)] = 'a'
	if t == 0:
		string = ''.join(l)
		print(string)


from math import floor, ceil
testcases = int(input())
for i in range(testcases):
	s = input()
	n = len(s)
	ans = [None] * n
	p1 = ceil(n / 2) - 1
	p2 = floor(n / 2)
	can_be_palindrome = True
	while p1 >= 0:
		if s[p1] == '.' and s[p2] == '.':
			ans[p1] = ans[p2] = 'a'
		elif s[p1] == '.':
			ans[p1] = ans[p2] = s[p2]
		elif s[p2] == '.':
			ans[p1] = ans[p2] = s[p1]
		else:
			ans[p1] = s[p1]
			ans[p2] = s[p2]
			if ans[p1] != ans[p2]:
				can_be_palindrome = False
				break
		p1 -= 1
		p2 += 1
	if can_be_palindrome:
		s = ''
		for j in range(n):
			s += ans[j]
		print(s)
	else:
		print(-1)


for _ in range(int(input())):
	l = list(input())
	for i in range(len(l)):
		if l[i] == '.':
			if l[i] == l[len(l) - 1 - i]:
				l[i] = 'a'
			else:
				l[i] = l[len(l) - 1 - i]
	if l == l[::-1]:
		for i in l:
			print(i, end='')
		print()
	else:
		print(-1)