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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for j in range(int(input())):\r\n    a=input()\r\n    x=list(a)\r\n    n=len(x)\r\n    am=0\r\n    if(n%2==0):\r\n        for i in range(n):\r\n            if(x[i]=="." or x[n-i-1]=="."):\r\n                if(x[i]=="." and x[n-i-1]!="."):\r\n                    x[i]=x[n-i-1]\r\n                elif(x[n-i-1]=="." and x[i]!="."):\r\n                    x[n-i-1]=x[i]\r\n                else:\r\n                    x[i]="a"\r\n                    x[n-i-1]="a"\r\n            elif(x[i]!=x[n-i-1]):\r\n                am=1\r\n                break\r\n    else:\r\n        b=n//2\r\n        for i in range(n):\r\n            if(b==i):\r\n                if(x[i]=="."):\r\n                    x[i]="a"\r\n                else:\r\n                    continue\r\n            elif(x[i] == "." or x[n - i - 1] == "."):\r\n                if (x[i] == "." and x[n - i - 1] != "."):\r\n                    x[i] = x[n - i - 1]\r\n                elif (x[n - i - 1] == "." and x[i] != "."):\r\n                    x[n - i - 1] = x[i]\r\n                else:\r\n                    x[i] = "a"\r\n                    x[n - i - 1] = "a"\r\n            elif(x[i]!=x[n-i-1]):\r\n                am=1\r\n                break\r\n    if(am==0):\r\n        print("".join(x))\r\n    else:\r\n        print(-1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13775