Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $26$ lowercase Latin letters will be arranged in some order.

Polycarp uses the same password $s$ on all websites where he is registered (it is bad, but he doesn't care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn't like to move his fingers while typing the password, so, for each pair of adjacent characters in $s$, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi... is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $s$, so, for example, the password cannot be password (two characters s are adjacent).

Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of test cases.

Then $T$ lines follow, each containing one string $s$ ($1 \le |s| \le 200$) representing the test case. $s$ consists of lowercase Latin letters only. There are no two adjacent equal characters in $s$.


-----Output-----

For each test case, do the following:

  if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);  otherwise, print YES (in upper case), and then a string consisting of $26$ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them. 


-----Example-----
Input
5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

Output
YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

Difficulty: interview

Starter code:

Solutions:
T = int(input())



def solve(S):
    res = [S[0]]
    pos = 0 # think...
    for s in S[1:]:
        # can we change?
        if 0 <= pos-1 < len(res) and res[pos-1] == s:
            pos = pos-1
        elif 0 <= pos+1 < len(res) and res[pos+1] == s:
            pos = pos+1
        elif pos == 0 and s not in res:
            res.insert(0, s) # pos is still 0
        elif pos == len(res)-1 and s not in res:
            res.append(s)
            pos += 1
        else: return None
    #print(''.join(res))
    for x in range(ord('a'), ord('z')+1):
        x = chr(x)
        if x not in res:
            res.append(x)
    return ''.join(res)

for _ in range(T):
    res = solve(input())
    if res is None:
        print('NO')
    else:
        print('YES')
        print(res)


#!python3
"""
Author: w1ld [at] inbox [dot] ru
"""

from collections import deque, Counter
import array
from itertools import combinations, permutations
from math import sqrt
# import unittest


def read_int():
    return int(input().strip())


def read_int_array():
    return [int(i) for i in input().strip().split(' ')]

######################################################

class Node:
    def __init__(self, c):
        self.c = c
        self.l = None
        self.r = None


tests = read_int()

for test in range(tests):
    s = input().strip()
    left = Node(s[0])
    x = left
    found = True
    used = set([x.c])
    for c in s[1:]:
        if x.c == c:
            continue
        if x.l and x.l.c == c:
            x = x.l
        elif x.r and x.r.c == c:
            x = x.r
        elif not x.l and c not in used:
            x.l = Node(c)
            used.add(c)
            x.l.r = x
            x = x.l
            left = x
        elif not x.r and c not in used:
            x.r = Node(c)
            used.add(c)
            x.r.l = x
            x = x.r
        else:
            found = False
            break

    if not found:
        print("NO")
    else:
        ans = []
        x = left
        while x:
            ans.append(x.c)
            x = x.r
        for c in 'abcdefghijklmnopqrstuvwxyz':
            if c not in used:
                ans.append(c)
        print("YES")
        print(''.join(ans))












for _ in range(int(input())):
    q=input()
    ans=q[0]
    test=[0]*26
    j=0
    c = 1
    for i in q[1:]:
        if j>0 and ans[j-1]==i:
            j-=1
            continue
        if j<len(ans)-1 and ans[j+1]==i:
            j+=1
            continue
        if j==0:
            ans=i+ans
            continue
        if j==len(ans)-1:
            ans+=i
            j+=1
            continue
        c=0
    for i in ans:test[ord(i)-97]+=1
    for i in range(26):
        if test[i]>1:c=0
        if test[i]==0:ans+=chr(i+97)
    if c:
        print('YES')
        print(ans)
    else:
        print('NO')

T = int(input())

def solve(s):
    kb = list()
    cursor = -1
    seen = set()
    for c in s:
        if c in seen:
            if cursor - 1 >= 0 and kb[cursor - 1] == c:
                cursor -= 1
            elif cursor + 1 < len(kb) and kb[cursor + 1] == c:
                cursor += 1
            else:
                print('NO')
                return
        else:
            if cursor not in [0, len(kb) - 1]:
                print('NO')
                return
            elif cursor == 0:
                kb.insert(0, c)
                cursor = 0
            else:
                kb.append(c)
                cursor = len(kb) - 1
            seen.add(c)
    print('YES')
    ans = ''.join(kb)
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c not in seen:
            ans += c
    print(ans)

for _ in range(T):
    solve(input())