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 = '\'\'\'input\r\n3\r\na.ba\r\nc...c\r\n...\r\n\'\'\'\r\nfrom collections import defaultdict as dd\r\nfrom collections import Counter as ccd\r\nfrom itertools import  permutations as pp\r\nfrom itertools import combinations as cc\r\nfrom random import randint as rd\r\nfrom bisect import bisect_left as bl\r\nfrom bisect import bisect_right as br\r\nimport heapq as hq\r\nfrom math import gcd\r\n\'\'\'\r\nAuthor : dhanyaabhirami\r\nHardwork beats talent if talent doesn\'t work hard\r\n\'\'\'\r\n\'\'\'\r\nStuck?\r\nSee github resources\r\nDerive Formula\r\nKmcode blog\r\nCP Algorithms Emaxx\r\n\'\'\'\r\nmod=pow(10,9) +7\r\ndef inp(flag=0):\r\n    if flag==0:\r\n        return list(map(int,input().strip().split(\' \')))\r\n    else:\r\n        return int(input())\r\n\r\n# Code credits\r\n# assert(debug()==true)\r\n# for _ in range(int(input())):\r\n\r\nt=inp(1)\r\nwhile t:\r\n    t-=1\r\n    \r\n    s=input().strip()\r\n    n=len(s)\r\n    s=list(s)\r\n    if n%2==1 and s[n//2]==\'.\':\r\n    \ts[n//2]=\'a\'\r\n    for i in range(n//2):\r\n    \tif s[i]==s[n-i-1]:\r\n    \t\tif s[i]==\'.\':\r\n    \t\t\ts[i]=\'a\'\r\n    \t\t\ts[n-i-1]=\'a\'\r\n    \t\telse:\r\n    \t\t\tcontinue\r\n    \telif s[i]==\'.\':\r\n    \t\ts[i]=s[n-i-1]\r\n    \telif s[n-i-1]==\'.\':\r\n    \t\ts[n-i-1]=s[i]\r\n    \telse:\r\n    \t\ts = -1\r\n    \t\tbreak\r\n    if s!=-1:\r\n    \ts="".join(s)\r\n    print(s)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14591