Problem: You are given a string s, consisting only of characters '0' or '1'. Let |s| be the length of s.

You are asked to choose some integer k (k > 0) and find a sequence a of length k such that: 

  * 1 ≤ a_1 < a_2 < ... < a_k ≤ |s|; 
  * a_{i-1} + 1 < a_i for all i from 2 to k. 



The characters at positions a_1, a_2, ..., a_k are removed, the remaining characters are concatenated without changing the order. So, in other words, the positions in the sequence a should not be adjacent.

Let the resulting string be s'. s' is called sorted if for all i from 2 to |s'| s'_{i-1} ≤ s'_i.

Does there exist such a sequence a that the resulting string s' is sorted?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Then the descriptions of t testcases follow.

The only line of each testcase contains a string s (2 ≤ |s| ≤ 100). Each character is either '0' or '1'.

Output

For each testcase print "YES" if there exists a sequence a such that removing the characters at positions a_1, a_2, ..., a_k and concatenating the parts without changing the order produces a sorted string.

Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

Example

Input


5
10101011011
0000
11111
110
1100


Output


YES
YES
YES
YES
NO

Note

In the first testcase you can choose a sequence a=[1,3,6,9]. Removing the underlined letters from "10101011011" will produce a string "0011111", which is sorted.

In the second and the third testcases the sequences are already sorted.

In the fourth testcase you can choose a sequence a=[3]. s'= "11", which is sorted.

In the fifth testcase there is no way to choose a sequence a such that s' is sorted.

Solution (in PYTHON3):

Solution:
import collections
import sys


def localmin():
    def recur(l, low, high, n):
        mid = (low + high) // 2
        while low != high:

            if l[mid] == 0 or l[mid - 1] == 0 or l[mid + 1] == 0:
                mid += 1
                continue
            # print(l[mid])
            if (mid > 0 and l[mid - 1] < l[mid]) or (mid < n - 1 and l[mid] > l[mid + 1]):
                low = mid + 1
                mid = (low + high) // 2
                # mid = (low + high) //2
            elif (mid < n - 1 and l[mid] < l[mid + 1]) or (mid > 0 and l[mid - 1] > l[mid]):
                high = mid
                mid = (low + high) // 2
        # print(l[low])
        return low + 1
        # mid = (low + high) // 2
        # if (mid == 0 or l[mid - 1] > l[mid]) and (mid == n - 1 or l[mid + 1] > l[mid]):
        #     return mid + 1
        # elif (mid > 0 and l[mid - 1] < l[mid]):
        #     return recur(l, low, mid, n)
        # return recur(l, mid + 1, high, n)

    num = int(input())
    l = [0] * num
    for i in range(1, num + 1):
        print('?', i, sep=' ')
        sys.stdout.flush()
        l[int(input()) - 1] = i
        if i == 101:
            break
    return '! ' + str(recur(l, 0, len(l) - 1, len(l) - 1))


# print(localmin())

def painting():
    num = int(input())
    l = input().split()
    pos = 0
    c = 0
    # pos1 = pos
    l1last = ''
    llast = ''
    while pos < num:
        if l[pos] != llast:
            llast = l[pos]
            pos1 = pos + 1
            c += 1
        while pos1 < num and l[pos1] == llast:
            pos1 += 1
        try:
            if pos1 - pos != 1 and l[pos1] != l1last:
                c += 1
                l1last = l[pos1 - 1]
        except:
            return c + 1
        pos = pos1
    return c


# print(painting())


def arena():
    case = int(input())
    for _ in range(case):
        num = int(input())
        l = sorted(list(map(int, input().split())))
        minn, *l = l
        for i, v in enumerate(l):
            if v > minn:
                print(len(l) - i)
                break
        else:
            print(0)


# arena()


def catcycle():
    case = int(input())
    for _ in range(case):
        spots, hour = map(int, input().split())
        if spots % 2:
            a = spots
            b = 1
            hour %= (spots * (spots // 2) + (spots // 2) - 1)
            for i in range(1, hour):
                a -= 1
                if (b + 1) % spots == a:
                    b += 2
                else:
                    b += 1
                if b > spots:
                    b = b % spots
                if a < 1:
                    a = spots

            print(b)
            # while hour >= 0:
            #     a -= 1
            #     if (b + 1) % spots == a:
            #         b += 2
            #     else:
            #         b += 1
            #     if b > spots:
            #         b = b % spots
            #     if a < 1:
            #         a = spots
            #     hour -= 1
            # b %= spots
            # print(b if b else 1)
        else:
            spot = hour % spots
            print(spot if spot else spots)


# catcycle()

def vanyafence():
    f, maxh = map(int, input().split())
    res = 0
    for i in input().split():
        if int(i) > maxh:
            res += 1
        res += 1
    return res


# print(vanyafence())


def antonanddanik():
    num = input()
    s = input()
    ac = s.count("A")
    dc = s.count('D')
    if dc == ac:
        return 'Friendship'
    return 'Anton' if ac > dc else 'Danik'


# print(antonanddanik())


def weight():
    a, b = map(int, input().split())
    for i in range(1, 10000):
        a *= 3
        b *= 2
        if a > b:
            return i


# print(weight())


def petyarain():
    num = int(input())
    l = input().split()
    ans = 0
    for i in range(num):
        c = 1
        for i1 in range(i - 1, -1, -1):
            if int(l[i1]) > int(l[i1 + 1]):
                break
            c += 1
        for i1 in range(i + 1, num):
            if int(l[i1 - 1]) < int(l[i1]):
                break
            c += 1
        ans = max(ans, c)
    return ans


# print(petyarain())

def findcrim():
    num, inp = map(int, input().split())
    thed = min(inp - 1, num - inp)
    l = list(map(int, input().split()))
    c = 0
    for i in range(1, thed + 1):
        if l[inp - i - 1] and l[inp + i - 1]:
            c += 2
    if thed == inp - 1:
        c += l[thed * 2 + 1:].count(1)
    else:
        c += l[:inp - thed - 1].count(1)
    return c if not l[inp - 1] else c + 1


# print(findcrim())


def burglarandmatch():
    maxn, boxs = map(int, input().split())
    l = sorted([list(map(int, input().split())) for _ in range(boxs)], key=lambda x: x[1], reverse=True)
    ans = 0
    for i in l:
        if maxn - i[0] < 0:
            ans += maxn * i[1]
            break
        ans += i[0] * i[1]
        maxn -= i[0]
    return ans


# print(burglarandmatch())


def caisajump():
    num = int(input()) + 1
    l = [0] + list(map(int, input().split()))
    energy = 0
    ans = 0
    for i in range(num - 1):
        ne = l[i] - l[i + 1]
        energy += ne
        if energy < 0:
            ans -= energy
            energy = 0
    return ans


# print(caisajump())


def tictac():
    def dicide(l):
        black = False
        white = False
        for i in l:
            if i.count("X") == 3:
                if black:
                    return False
                black = True
            elif i.count('O') == 3:
                if white:
                    return False
                white = True
        for i in range(len(l)):
            bc = 0
            wc = 0
            for i1 in range(len(l)):
                if l[i1][i] == 'X':
                    bc += 1
                elif l[i1][i] == 'O':
                    wc += 1
            if bc == 3:
                if black:
                    return False
                black = True
            elif wc == 3:
                if white:
                    return False
                white = True
        bc = 0
        wc = 0
        for i in range(3):
            if l[i][i] == 'X':
                bc += 1
            if l[i][i] == 'O':
                wc += 1
        if bc == 3:
            if black:
                return False
            black = True
        elif wc == 3:
            if white:
                return False
            white = True
        if l[0][2] == 'X' and l[1][1] == 'X' and l[2][0] == 'X':
            if black:
                return False
            black = True
        elif l[0][2] == 'O' and l[1][1] == 'O' and l[2][0] == 'O':
            if white:
                return False
            white = True

        return False if white and black else True

    num = int(input())
    for _ in range(num):
        xc = 0
        oc = 0
        lar = []
        for i in range(3):
            l = input()
            xc += l.count("X")
            oc += l.count('O')
            lar.append(l)
        if oc > xc or not dicide(lar) or oc < xc - 1:
            print('no')
        else:
            print('yes')
        if _ != num - 1:
            s = input()


# tictac()
from copy import deepcopy


def change(pos, pos1, l, c):
    return l[:pos] + [l[pos][:pos1] + c + l[pos][pos1 + 1:]] + l[pos + 1:]


# print(change(0,1,['123','143','145'],'5'))
def tictac1():
    def dicide(l):
        for i in l:
            if i.count("X") == 3:
                return True
            elif i.count('O') == 3:
                return True
        for i in range(len(l)):
            bc = 0
            wc = 0
            for i1 in range(len(l)):
                if l[i1][i] == 'X':
                    bc += 1
                elif l[i1][i] == 'O':
                    wc += 1
            if bc == 3:
                return True
            elif wc == 3:
                return True
        bc = 0
        wc = 0
        for i in range(3):
            if l[i][i] == 'X':
                bc += 1
            if l[i][i] == 'O':
                wc += 1
        if bc == 3:
            return True
        elif wc == 3:
            return True
        if l[0][2] == 'X' and l[1][1] == 'X' and l[2][0] == 'X':
            return True

        elif l[0][2] == 'O' and l[1][1] == 'O' and l[2][0] == 'O':
            return True

    his = set()
    todo = [[['...', '...', '...'], 'X']]
    while todo:
        l, now = todo.pop()
        tl = tuple(l)
        if tl not in his:
            his.add(tl)
        else:
            continue
        if dicide(l):
            continue
        if now == 'X':
            for i in range(3):
                for i1 in range(3):
                    if l[i][i1] == '.':
                        todo.append([change(i, i1, l, now), 'O'])
        else:
            for i in range(3):
                for i1 in range(3):
                    if l[i][i1] == '.':
                        todo.append([change(i, i1, l, now), 'X'])
    n = int(input())
    for i in range(n):
        print('yes' if tuple(input() for _ in range(3)) in his else 'no')
        if i != n - 1:
            input()


# tictac1()


def tictac2():
    def dicide(l):
        for i in l:
            if '.' in i:
                break
        else:
            return True
        for i in l:
            if i.count("X") == 3:
                return True
            elif i.count('O') == 3:
                return True
        for i in range(len(l)):
            bc = 0
            wc = 0
            for i1 in range(len(l)):
                if l[i1][i] == 'X':
                    bc += 1
                elif l[i1][i] == 'O':
                    wc += 1
            if bc == 3:
                return True
            elif wc == 3:
                return True
        bc = 0
        wc = 0
        for i in range(3):
            if l[i][i] == 'X':
                bc += 1
            if l[i][i] == 'O':
                wc += 1
        if bc == 3:
            return True
        elif wc == 3:
            return True
        if l[0][2] == 'X' and l[1][1] == 'X' and l[2][0] == 'X':
            return True
        elif l[0][2] == 'O' and l[1][1] == 'O' and l[2][0] == 'O':
            return True

    his = set()
    todo = [[['...', '...', '...'], 'X']]
    while todo:
        l, now = todo.pop()
        if tuple(l) in his:
            continue
        if dicide(l):
            his.add(tuple(l))
            continue
        if now == 'X':
            for i in range(3):
                for i1 in range(3):
                    if l[i][i1] == '.':
                        todo.append([change(i, i1, l, now), 'O'])
        else:
            for i in range(3):
                for i1 in range(3):
                    if l[i][i1] == '.':
                        todo.append([change(i, i1, l, now), 'X'])
    print(his)
    while True:
        s = input()
        if s == 'end':
            break

        print('valid' if tuple([s[:3], s[3:6], s[6:9]]) in his else 'invalid')


# tictac2()


def tictac3():
    his = {('OXX', 'O..', 'OX.'), ('X..', 'OXO', 'OXX'), ('O..', '.OX', 'XXO'), ('.OX', 'XXX', 'OO.'),
           ('XOX', '.XO', 'O.X'), ('OXX', 'O.X', 'OXO'), ('.OX', 'XOX', '.O.'), ('OXX', 'XX.', 'OOO'),
           ('X.O', 'XOO', 'OXX'), ('X.O', 'OOX', 'OXX'), ('..O', 'XOX', 'O.X'), ('...', 'O.O', 'XXX'),
           ('.XO', 'OO.', 'XXX'), ('OOO', 'XXO', '.XX'), ('XXX', 'OO.', 'XO.'), ('OOX', '.X.', 'X..'),
           ('.X.', '.XO', 'OX.'), ('OX.', 'XXX', 'O.O'), ('XXO', 'XXO', '.OO'), ('O.X', 'OXX', 'X.O'),
           ('OXX', 'XO.', 'OXO'), ('X.O', 'XOX', 'O..'), ('..X', 'OOO', 'X.X'), ('O.X', 'OXO', 'OXX'),
           ('.O.', 'XO.', 'XOX'), ('OXX', '.OO', 'XXO'), ('.O.', 'XOX', 'XO.'), ('XXX', 'O..', 'OOX'),
           ('XXX', 'O..', 'XOO'), ('.XO', '.XO', 'X.O'), ('X..', 'XO.', 'X.O'), ('O.O', '.XO', 'XXX'),
           ('.X.', 'OX.', '.XO'), ('.XX', 'OXO', 'XO.'), ('.XX', 'OXX', 'OOO'), ('X.O', 'XXX', 'O.O'),
           ('OOX', '.OX', 'XXO'), ('..X', 'OOX', 'OXX'), ('.XO', 'XXX', 'OO.'), ('.OO', 'XO.', 'XXX'),
           ('XXX', 'O.O', 'X.O'), ('XXO', '..O', '.XO'), ('.OX', 'OX.', 'XXO'), ('XXO', 'X..', 'XOO'),
           ('OXO', 'X.O', 'XXO'), ('XOX', 'XO.', 'OOX'), ('XO.', 'XO.', 'X..'), ('XOX', 'OX.', '.OX'),
           ('OOX', '.XO', 'XX.'), ('XXX', '..O', 'OOX'), ('XXX', '..O', 'XOO'), ('X.X', 'XOX', 'OOO'),
           ('XOO', '..O', 'XXX'), ('OOX', '..O', 'XXX'), ('XXX', '.XO', '.OO'), ('OOX', '.X.', 'XXO'),
           ('X.O', 'XXX', 'OO.'), ('.X.', 'OX.', 'OX.'), ('XXX', 'XO.', 'O.O'), ('OOO', 'X..', 'X.X'),
           ('XOO', '.X.', 'XOX'), ('OOX', '.X.', 'XOX'), ('XXX', '.O.', '..O'), ('O.X', 'O.X', 'XOX'),
           ('XO.', 'XXX', '.OO'), ('..O', '.O.', 'XXX'), ('O..', 'OXX', 'O.X'), ('XOO', 'XXX', '..O'),
           ('..X', 'OXO', 'XXO'), ('OOX', 'XXX', '..O'), ('..X', 'OOX', '..X'), ('.OX', 'OX.', 'XOX'),
           ('XXX', 'O.O', '.OX'), ('XXO', 'XX.', 'OOO'), ('O.X', '.OX', '.XO'), ('XXX', '.OO', 'O.X'),
           ('XOO', 'XOX', '.OX'), ('OXO', 'XXO', 'OXX'), ('OX.', 'XOX', 'XOO'), ('XOO', 'XXO', 'X..'),
           ('OOX', 'XXO', 'X..'), ('OXO', 'O.X', 'OXX'), ('.XX', 'O.X', 'OOX'), ('.OX', '.OX', 'XO.'),
           ('.OX', 'XXX', 'O.O'), ('OOO', 'OXX', '.XX'), ('X.O', '.XO', 'X.O'), ('XOX', 'OX.', 'XO.'),
           ('XXO', 'OO.', 'OXX'), ('XXO', 'X.X', 'OOO'), ('..X', '..X', 'OOX'), ('XXO', '.XO', 'XOO'),
           ('OXX', 'OXX', 'O.O'), ('XOO', '.XO', 'XXO'), ('XO.', 'XOX', 'X.O'), ('XOX', 'OOX', 'XO.'),
           ('XOO', 'X..', 'XOX'), ('XO.', '.X.', 'O.X'), ('OOO', 'XXO', 'XX.'), ('OXX', 'OXO', '.X.'),
           ('OOO', 'X.X', 'XOX'), ('XXX', 'OOX', 'OOX'), ('XXX', 'XOO', 'OOX'), ('X..', '.XO', 'O.X'),
           ('X.O', 'OX.', 'XOX'), ('OXX', 'OOO', 'XX.'), ('XXX', 'OOX', 'XOO'), ('XXX', 'XOO', 'XOO'),
           ('XOX', 'XOX', 'OXO'), ('O.X', 'XO.', 'X.O'), ('O.O', '...', 'XXX'), ('XOX', '.OX', '.O.'),
           ('XXX', 'OOX', '.O.'), ('OXO', '.XO', 'XX.'), ('XXX', 'XOO', '.O.'), ('XXX', '..O', 'OXO'),
           ('O.X', 'OX.', 'OX.'), ('OXX', 'O..', 'O.X'), ('X.O', 'X.X', 'XOO'), ('X.O', 'XOX', 'X.O'),
           ('..O', 'O..', 'XXX'), ('...', 'XXX', 'O.O'), ('..X', 'OXO', 'X..'), ('OXX', '.OX', '.OX'),
           ('X.O', 'OXX', '.OX'), ('OXX', 'OX.', 'XO.'), ('XXX', '.OX', 'OO.'), ('.X.', '.XX', 'OOO'),
           ('.XX', 'OOO', 'XXO'), ('OXX', 'OXX', 'OO.'), ('.XO', 'OX.', 'OXX'), ('.XO', 'OXO', '.XX'),
           ('OO.', 'XXX', 'OX.'), ('XO.', 'XO.', '.OX'), ('OOX', '..X', 'XOX'), ('OOO', 'X.X', 'XXO'),
           ('X.O', 'X..', 'X.O'), ('X..', 'XOX', 'XOO'), ('X.O', 'OXO', 'X.X'), ('XXO', 'OOX', 'XXO'),
           ('OOX', 'XXO', 'XOX'), ('XXO', 'OX.', 'O.X'), ('XOO', 'XXO', 'XOX'), ('OX.', 'OXX', 'OOX'),
           ('OOX', 'OX.', 'OXX'), ('.XO', 'XO.', 'OX.'), ('XXX', '.OO', 'XO.'), ('.XX', 'OXO', 'OX.'),
           ('XXO', 'OXO', '.X.'), ('XXX', '...', 'O.O'), ('XOO', 'XO.', 'OXX'), ('.OX', 'OXO', 'XX.'),
           ('XXO', 'XOX', 'XOO'), ('XXX', '.OO', '.OX'), ('.OX', 'XXX', '.OO'), ('XO.', 'X..', 'X.O'),
           ('XX.', 'OXO', '.OX'), ('XX.', 'XOO', 'XO.'), ('X.X', '.XO', 'OOX'), ('OOX', 'X.X', '.OX'),
           ('OXO', '..O', 'XXX'), ('X.X', '.XO', 'XOO'), ('XXO', 'XO.', 'OOX'), ('OXO', 'XXX', 'O..'),
           ('XX.', '.XO', 'OXO'), ('XXX', 'O.O', '.XO'), ('.OO', 'XOX', 'XOX'), ('XO.', 'XX.', 'OOX'),
           ('X.X', 'OOO', '..X'), ('O.X', '.XO', 'XXO'), ('XO.', 'XX.', 'XOO'), ('.XO', 'O.O', 'XXX'),
           ('...', 'OO.', 'XXX'), ('OOO', 'OXX', 'XX.'), ('OX.', 'XO.', '.XO'), ('.OO', '.XO', 'XXX'),
           ('XXO', 'XOO', 'XOX'), ('XXO', 'OOX', 'XOX'), ('.OX', 'O.X', '..X'), ('XXX', '.OO', '...'),
           ('O.X', '.XO', 'XOX'), ('OO.', '.XO', 'XXX'), ('XXX', 'O.O', 'O.X'), ('OOO', 'XX.', 'OXX'),
           ('XO.', 'OXO', '.XX'), ('O.X', 'XOX', '..O'), ('XOO', '.X.', 'OXX'), ('XX.', 'XOO', 'X.O'),
           ('OXO', 'XXX', '..O'), ('OXO', '.X.', '.X.'), ('O..', 'XOX', 'X.O'), ('XX.', 'X..', 'OOO'),
           ('OXO', 'XXO', 'XOX'), ('OOX', 'O.X', '.XX'), ('OXX', 'OXO', 'O.X'), ('.XO', '.OO', 'XXX'),
           ('XXO', 'OOX', 'O.X'), ('XXO', 'XOO', 'O.X'), ('.O.', 'XXX', 'OXO'), ('XXO', 'OXO', 'X.O'),
           ('XOX', 'XOO', 'X..'), ('XXX', 'OOX', '..O'), ('XXX', 'XOO', '..O'), ('...', 'XXX', 'OO.'),
           ('XX.', 'OX.', 'OXO'), ('.XO', '.O.', 'OXX'), ('OXX', 'OXO', 'X..'), ('O.X', 'XXO', 'XO.'),
           ('XXX', '.OX', 'O.O'), ('OX.', 'OXO', '.XX'), ('X.O', '.XO', '..X'), ('OOO', 'XOX', 'X.X'),
           ('XXO', '.X.', 'OXO'), ('X.O', 'OXO', 'XXO'), ('X.O', 'X..', 'XO.'), ('XO.', 'O.O', 'XXX'),
           ('.XO', 'XXO', 'XOO'), ('OO.', 'OXX', 'OXX'), ('XOX', '.XO', '.OX'), ('OX.', 'OXO', 'XX.'),
           ('..X', 'XOX', 'OOX'), ('OXO', 'OX.', 'XX.'), ('X..', 'X..', 'XOO'), ('XO.', 'X.O', 'X..'),
           ('XOO', 'XXX', '.O.'), ('O.O', 'XOX', 'OXX'), ('OOX', 'XXX', '.O.'), ('OO.', 'XXX', 'O.X'),
           ('XXX', '.O.', '.O.'), ('..X', 'OOO', 'XX.'), ('O.X', '.O.', 'XXO'), ('XXO', 'O.O', 'XXO'),
           ('..O', 'XXO', 'X.O'), ('XXX', '.O.', 'OOX'), ('.O.', '.O.', 'XXX'), ('OX.', 'XXO', 'OX.'),
           ('.XO', '.XO', 'OXX'), ('XXX', '.O.', 'XOO'), ('OX.', 'O.X', 'O.X'), ('O.X', 'XX.', 'XOO'),
           ('XXX', '...', 'OO.'), ('.OX', 'XOX', 'XOO'), ('OX.', 'O..', 'OXX'), ('O.O', 'OXX', 'OXX'),
           ('X.O', 'XXO', 'O.X'), ('O.X', 'OXX', 'OXO'), ('X.X', 'OOO', 'XXO'), ('X..', 'OX.', 'O.X'),
           ('.XO', '..O', 'XXO'), ('X.O', 'XXX', '.OO'), ('.OO', 'XXX', 'X.O'), ('OOO', 'XX.', 'XXO'),
           ('.O.', 'OXO', 'XXX'), ('XXO', '.XO', 'O.X'), ('.OX', 'XO.', '.OX'), ('XOX', 'OOO', '.XX'),
           ('X.X', '..X', 'OOO'), ('OOX', '.XX', 'X.O'), ('X.X', 'OOO', '.X.'), ('O..', 'XXX', 'OOX'),
           ('XOO', 'XXO', '.XO'), ('O..', 'XXX', 'XOO'), ('O.X', 'OXO', 'X.X'), ('XO.', 'XXO', 'X.O'),
           ('XOX', 'X.O', 'XO.'), ('X.O', 'OO.', 'XXX'), ('XXX', 'O.O', '...'), ('.OX', 'OXX', 'X.O'),
           ('OX.', 'XO.', 'X.O'), ('XXO', 'XXO', 'OOX'), ('.XO', 'OXO', 'XX.'), ('XXX', '.OO', 'OX.'),
           ('XX.', 'X.O', 'XOO'), ('..X', '.X.', 'XOO'), ('OXX', 'OOO', '.XX'), ('XXX', '...', '.OO'),
           ('XOO', 'OX.', 'X.X'), ('OOX', 'OX.', 'X.X'), ('XOO', 'XOO', 'XXX'), ('OOX', 'XOO', 'XXX'),
           ('XOO', 'OOX', 'XXX'), ('O.X', 'O.X', '..X'), ('O..', 'OXX', 'OX.'), ('OOX', 'OOX', 'XXX'),
           ('XOX', 'X..', 'XOO'), ('.O.', '..O', 'XXX'), ('O.X', 'XOX', 'O.X'), ('.XO', 'XXX', '.OO'),
           ('XXO', 'X.O', '..O'), ('O.X', '..X', 'O.X'), ('O..', 'XXX', 'OXO'), ('OOO', 'XX.', 'XOX'),
           ('XX.', 'OOO', '..X'), ('.XX', 'X..', 'OOO'), ('OX.', '.OX', 'X.O'), ('OXX', '.XO', 'X.O'),
           ('XXX', 'O.O', 'XO.'), ('X.O', 'XO.', 'OX.'), ('..O', '.OX', 'OXX'), ('X.X', 'OOX', '.OX'),
           ('OXO', 'XOO', 'XXX'), ('OXO', 'OOX', 'XXX'), ('O.O', '.OX', 'XXX'), ('O.O', 'XXO', 'XXO'),
           ('XXO', '.OO', 'XXO'), ('OXX', 'OOX', '.XO'), ('OXX', 'XOO', '.XO'), ('O.X', 'OOX', '.XX'),
           ('XXX', '.OO', '.XO'), ('XO.', 'X.X', 'XOO'), ('.OX', 'OO.', 'XXX'), ('XXO', 'XOX', 'O.O'),
           ('OXO', 'XX.', 'OX.'), ('.OX', 'O.O', 'XXX'), ('.XX', 'OXO', 'X.O'), ('.OX', 'XX.', 'XOO'),
           ('O.X', 'O.X', 'OX.'), ('O..', 'XXX', '.O.'), ('O..', 'XOX', '.XO'), ('X.X', 'OXO', 'O.X'),
           ('X.O', 'OXX', 'O.X'), ('XOO', 'X.O', 'X.X'), ('OXO', 'XX.', '.XO'), ('XOX', 'OXO', 'OXX'),
           ('OOX', '..X', '..X'), ('XOX', 'XOO', 'XXO'), ('OOO', '.X.', 'X.X'), ('XOX', 'OOX', 'XXO'),
           ('XXO', 'XO.', 'O..'), ('OOO', '.XX', 'OXX'), ('OXX', '.OX', 'O.X'), ('XXO', '.XO', 'OX.'),
           ('XXO', '.X.', 'OOX'), ('.OO', 'XXO', 'XXO'), ('OOO', '..X', 'X.X'), ('X..', 'XO.', 'XO.'),
           ('.OX', 'O.X', 'OXX'), ('O.X', 'XOO', 'XXO'), ('O.X', 'OOX', 'XXO'), ('XXX', 'OO.', 'X.O'),
           ('O.X', 'XO.', '.XO'), ('OO.', 'O.X', 'XXX'), ('X.O', 'XO.', 'XOX'), ('XXO', 'OOO', '.XX'),
           ('.XO', '.XO', '.X.'), ('X.X', 'OOO', 'OXX'), ('...', 'XXX', '.OO'), ('.O.', 'XXX', '..O'),
           ('OXX', 'O.X', 'O..'), ('.X.', 'OOO', '.XX'), ('O.X', 'OX.', 'XXO'), ('XOX', '.O.', 'XO.'),
           ('O.X', 'XOX', 'XOO'), ('O..', 'OXO', 'XXX'), ('X.O', 'XXO', 'XO.'), ('O.X', 'O.O', 'XXX'),
           ('X.O', 'X.O', 'X..'), ('.OX', '..X', '.OX'), ('XXX', 'OO.', 'O.X'), ('.O.', '.OX', 'XOX'),
           ('X.O', 'OX.', '..X'), ('XOX', '.XO', 'XO.'), ('O.X', 'OXX', 'XO.'), ('OO.', 'XXX', 'XO.'),
           ('XO.', 'XXX', 'OO.'), ('.OX', '.XO', 'XXO'), ('OO.', 'XOX', 'XOX'), ('OOO', 'XXO', 'X.X'),
           ('X.O', 'XOO', 'XX.'), ('XO.', 'X.O', 'XOX'), ('XXO', '.OX', 'OOX'), ('XO.', '.XO', 'OXX'),
           ('OOX', 'XOX', 'OXX'), ('XOX', 'OO.', 'XOX'), ('..X', 'OOO', '.XX'), ('OX.', '.X.', '.XO'),
           ('XO.', 'OOX', 'XOX'), ('..X', 'OX.', 'XO.'), ('OXX', 'X.X', 'OOO'), ('OX.', 'OXX', 'O..'),
           ('XOX', 'OX.', 'O.X'), ('OXO', 'OXX', 'O.X'), ('OXX', '.XO', '.XO'), ('XOO', '.XO', '.XX'),
           ('X.X', 'OXX', 'OOO'), ('XOX', 'O.X', '.OX'), ('OOO', 'X.X', 'X..'), ('.OO', 'X.O', 'XXX'),
           ('X.X', 'OOX', 'O.X'), ('OXO', 'XOX', 'XOX'), ('..O', 'XXX', 'OXO'), ('OXO', 'XOX', '.XO'),
           ('X.X', 'OX.', 'OOX'), ('OXX', 'OXO', 'XOX'), ('..X', 'OOX', 'XOX'), ('OXO', '.XO', '.XX'),
           ('XOO', 'XO.', 'X.X'), ('..O', 'X.O', 'XXO'), ('X.X', 'OX.', 'XOO'), ('XOO', 'XX.', 'X.O'),
           ('OOX', 'XX.', 'X.O'), ('X.O', 'XOO', 'X.X'), ('XX.', 'OXX', 'OOO'), ('O.O', 'XXX', 'X.O'),
           ('XOO', '.OX', 'OXX'), ('.OX', '.XO', 'XOX'), ('OOO', 'XX.', '.X.'), ('OXO', 'XOX', 'O.X'),
           ('XO.', 'XXX', 'O.O'), ('OXO', 'XO.', 'OXX'), ('XX.', '.XO', 'OOX'), ('XO.', 'OO.', 'XXX'),
           ('X.X', 'OXO', '.OX'), ('OXO', 'OXO', 'XXX'), ('XOO', 'XXO', '..X'), ('XXX', 'O..', 'O..'),
           ('..X', 'XX.', 'OOO'), ('O..', 'OX.', 'OXX'), ('OXX', '.XO', 'OX.'), ('.O.', 'XXX', '.O.'),
           ('OXO', '.OX', 'OXX'), ('.XO', 'XOX', 'OOX'), ('OXO', '.O.', 'XXX'), ('XO.', '.O.', 'XOX'),
           ('OOO', 'X..', '.XX'), ('..X', 'O.X', '.OX'), ('..X', '.OX', 'O.X'), ('OX.', '.X.', 'OX.'),
           ('XOO', 'XX.', 'XO.'), ('OOX', 'XX.', 'XO.'), ('OOO', '..X', 'XX.'), ('XXX', 'X.O', 'O.O'),
           ('.XX', 'OOX', '.OX'), ('OXX', 'OXO', 'XXO'), ('O.O', 'XXX', 'XO.'), ('XOX', 'OXO', 'XXO'),
           ('XXO', 'OX.', '.XO'), ('XX.', 'OOO', 'X..'), ('X.X', 'OXO', 'X.O'), ('.X.', 'OXO', 'XXO'),
           ('OXO', '.XX', '.XO'), ('OXO', 'XOX', 'OX.'), ('XXO', 'OXX', 'OOX'), ('XXO', 'OXX', 'XOO'),
           ('X.O', 'XXO', '.OX'), ('O.X', '.OX', 'X.O'), ('O.X', 'XOX', 'OXO'), ('..X', 'X.X', 'OOO'),
           ('OXO', 'O..', 'XXX'), ('X.O', 'XOX', 'OOX'), ('XOX', '.XX', 'OOO'), ('XOX', 'OXO', 'XOX'),
           ('X..', 'XOO', 'X..'), ('XXO', 'OX.', 'OX.'), ('OX.', 'XXX', 'OO.'), ('.OX', 'X.X', 'OOX'),
           ('.OX', 'OOX', 'X.X'), ('XXX', 'OOX', 'OXO'), ('XXO', '.OX', 'OXO'), ('XXX', 'XOO', 'OXO'),
           ('XXO', '.XO', '.OX'), ('.XO', 'XO.', 'O.X'), ('..X', 'OX.', 'X.O'), ('XOO', 'XXX', 'OOX'),
           ('OOX', 'XXX', 'OOX'), ('XOO', 'XXX', 'XOO'), ('OOX', 'XXX', 'XOO'), ('OXX', 'O.X', '.OX'),
           ('X..', 'OXO', '..X'), ('OOX', '.OX', '.XX'), ('OO.', 'XXX', '.OX'), ('.XX', 'XXO', 'OOO'),
           ('XOO', '.O.', 'XXX'), ('OOX', '.O.', 'XXX'), ('OX.', '.O.', 'XXO'), ('X..', 'OOO', '.XX'),
           ('XXX', 'XO.', '.OO'), ('.XO', 'XXX', 'O.O'), ('X.O', '.XO', 'XOX'), ('XO.', 'XOX', '.O.'),
           ('.OX', 'O.X', 'XOX'), ('.XX', 'OOO', 'OXX'), ('.O.', 'XOO', 'XXX'), ('O.X', 'XOX', '.OX'),
           ('.O.', 'OOX', 'XXX'), ('XOO', 'XOX', 'XXO'), ('OXX', 'XOX', '.OO'), ('O.O', 'O.X', 'XXX'),
           ('OO.', 'XXX', 'X.O'), ('OX.', 'XOX', 'OXO'), ('OOX', 'XOX', 'XO.'), ('X..', 'OOO', 'XX.'),
           ('..X', 'XXO', 'XOO'), ('OXX', '.OX', 'XOO'), ('XO.', 'XOO', 'X.X'), ('.XO', 'OX.', '.X.'),
           ('O.X', 'XXX', 'O.O'), ('O..', 'O.X', 'OXX'), ('XO.', '.OX', '.OX'), ('OO.', 'OX.', 'XXX'),
           ('XOX', '.XO', 'X.O'), ('OX.', 'XOO', 'XXO'), ('.OO', 'XXX', 'O.X'), ('OXX', 'OOX', '..X'),
           ('..X', 'OXX', 'OOX'), ('.OO', 'O.X', 'XXX'), ('OX.', 'OOX', 'XXO'), ('OOX', 'XO.', 'XXO'),
           ('OXO', '.XX', 'OX.'), ('..X', 'OXX', 'XOO'), ('OOX', 'X.X', 'O.X'), ('X.O', 'OXO', '.XX'),
           ('XXO', '.O.', 'O.X'), ('O..', '..O', 'XXX'), ('..X', '.OX', '.OX'), ('..X', 'O.X', 'O.X'),
           ('..O', 'XXX', 'O..'), ('.XO', 'OX.', 'XXO'), ('XX.', 'XXO', 'OOO'), ('OOX', 'XO.', 'XOX'),
           ('.XX', 'OOX', 'O.X'), ('XXX', 'OXO', '.O.'), ('OXO', 'XXO', '.X.'), ('.XX', 'OX.', 'XOO'),
           ('.XX', '.X.', 'OOO'), ('XOO', 'OXX', 'OXX'), ('OXO', 'XXX', 'OXO'), ('OXX', '.X.', 'OXO'),
           ('O..', 'O..', 'XXX'), ('XOX', 'OXX', 'XOO'), ('X..', 'X.O', 'XO.'), ('XOX', 'OXX', 'OOX'),
           ('.XO', '.X.', '.XO'), ('OXX', 'XOO', 'XOX'), ('OXX', 'OOX', 'XOX'), ('XOO', '.XX', '.OX'),
           ('OOX', '.XX', '.OX'), ('OX.', '.XO', '.X.'), ('..X', 'OXO', 'XOX'), ('XOO', '.OX', 'XOX'),
           ('XOX', '.X.', 'OOX'), ('XOX', '.X.', 'XOO'), ('X.X', 'XOO', 'X.O'), ('..O', 'XXX', '..O'),
           ('O.X', '.X.', 'XO.'), ('.OX', 'OXX', '.OX'), ('.XX', 'OOO', '..X'), ('XO.', 'XO.', 'XXO'),
           ('.OX', '.O.', 'XOX'), ('XOO', 'X.O', 'XX.'), ('.OO', 'XOX', 'OXX'), ('XXX', 'O..', 'OXO'),
           ('XO.', 'XXO', '.OX'), ('XXX', 'X.O', '.OO'), ('.OX', 'XXO', 'XO.'), ('OXX', '.XO', 'XO.'),
           ('OXO', 'XO.', 'XXO'), ('XO.', 'OXO', 'X.X'), ('.O.', 'XXX', 'O..'), ('X.O', 'X.O', '.XO'),
           ('XO.', 'OXX', 'O.X'), ('XXX', 'OO.', '.OX'), ('.OX', '..X', 'O.X'), ('XOX', 'X.O', 'X.O'),
           ('OOO', 'X.X', '..X'), ('XO.', 'XXO', 'XO.'), ('XOO', 'X..', 'X..'), ('OXO', '.OX', 'XXO'),
           ('XXX', 'O..', '.O.'), ('..X', '.XX', 'OOO'), ('XXX', 'OX.', 'OO.'), ('XXX', 'O.X', '.OO'),
           ('.OX', 'OXX', 'XO.'), ('.XO', 'X.O', '.XO'), ('XX.', 'XOX', 'OOO'), ('.XO', '.X.', 'OX.'),
           ('OOX', '.XX', 'XO.'), ('OX.', '.XX', 'OXO'), ('XXO', 'XO.', 'XO.'), ('OOO', 'XOX', '.XX'),
           ('.XO', 'XOO', 'OXX'), ('.XO', 'OOX', 'OXX'), ('.OX', '.XX', 'OOX'), ('OXX', 'OOX', 'OX.'),
           ('XXO', '.O.', 'OX.'), ('.OX', '.XX', 'XOO'), ('X.O', '.X.', 'O.X'), ('OXX', 'XO.', 'XOO'),
           ('.OO', 'XXX', 'XO.'), ('OX.', 'OOX', 'OXX'), ('OXO', 'XXO', 'X.O'), ('O..', 'XXX', '..O'),
           ('X..', 'XOO', 'XXO'), ('XOX', 'XOX', 'OO.'), ('OOX', 'XXO', 'XXO'), ('OXX', 'OX.', 'OOX'),
           ('.OX', '.X.', 'XO.'), ('OX.', 'OX.', 'XXO'), ('XXX', 'OOX', 'O..'), ('.OX', 'OXO', 'X.X'),
           ('XXX', 'OXO', 'OXO'), ('X.O', '.XO', 'OXX'), ('.OO', '.OX', 'XXX'), ('O.X', 'XXX', 'OO.'),
           ('OXX', 'XXO', 'OOX'), ('OXX', 'XXO', 'XOO'), ('X.X', 'XXO', 'OOO'), ('XXX', 'XOO', 'O..'),
           ('X..', 'XOO', 'XOX'), ('.XX', 'OOO', 'XOX'), ('.X.', 'OOO', 'XX.'), ('.X.', 'OXX', 'OXO'),
           ('OX.', 'O.X', 'OX.'), ('..O', 'XOX', 'OX.'), ('..X', '.XO', 'X.O'), ('OXO', 'XXX', 'OOX'),
           ('XXO', 'OOO', 'XX.'), ('.X.', 'OXO', 'OXX'), ('OXO', 'XXX', 'XOO'), ('OXX', '.X.', 'XOO'),
           ('XX.', 'OX.', 'OOX'), ('OXO', 'XXX', '.O.'), ('O.X', 'OXX', 'O..'), ('OXX', 'OO.', 'XXO'),
           ('XOX', 'OXX', 'OXO'), ('OOO', '.X.', 'XX.'), ('XXO', 'OXO', '..X'), ('XOO', 'O..', 'XXX'),
           ('OOX', 'O..', 'XXX'), ('.X.', 'X.X', 'OOO'), ('.XX', 'OX.', 'OXO'), ('OO.', 'XO.', 'XXX'),
           ('OOO', 'XOX', 'XX.'), ('.OO', 'XXX', '...'), ('.OX', 'XOX', 'O.X'), ('.XO', '.XX', 'OXO'),
           ('.OX', 'XO.', 'XO.'), ('OXX', '.OX', 'OXO'), ('..O', 'XOO', 'XXX'), ('..O', 'OOX', 'XXX'),
           ('XOX', 'O.X', 'O.X'), ('X.O', 'XX.', 'OOX'), ('X.O', 'XX.', 'XOO'), ('O.O', 'X.O', 'XXX'),
           ('O..', '.O.', 'XXX'), ('O.X', 'OXO', 'XX.'), ('OXX', 'O.O', 'OXX'), ('XOO', 'X..', 'XXO'),
           ('XOX', 'OOO', 'X.X'), ('XO.', '.OX', 'XO.'), ('XOO', 'X.X', 'X.O'), ('.XX', '..X', 'OOO'),
           ('O.O', 'XOX', 'XXO'), ('O.X', 'XXO', 'X.O'), ('X..', '.X.', 'OOX'), ('O.O', 'XXX', '...'),
           ('XX.', 'OOO', 'OXX'), ('X.O', '.OX', 'OX.'), ('OXX', 'OOO', 'X.X'), ('OXX', 'XO.', '..O'),
           ('XOO', 'OX.', '.XX'), ('OX.', 'XXO', '.XO'), ('O..', 'XXX', 'O..'), ('.OX', 'OXX', 'O.X'),
           ('XXO', '..O', 'X.O'), ('XXX', 'OX.', 'O.O'), ('XO.', 'XXO', 'O.X'), ('O.X', 'OO.', 'XXX'),
           ('X.O', 'XXO', '..O'), ('OXX', 'XOO', 'OXX'), ('XOX', 'XX.', 'OOO'), ('.OX', '.OX', '..X'),
           ('XXX', 'O.O', 'OX.'), ('X.O', '.X.', '.OX'), ('XXO', 'XOO', '.XO'), ('X.X', 'X..', 'OOO'),
           ('XO.', 'OXX', '.OX'), ('OX.', 'XX.', 'OXO'), ('XXO', 'XXO', 'O.O'), ('O.O', 'XXX', '.OX'),
           ('OX.', '.XO', 'XXO'), ('O.X', 'X.X', 'OOX'), ('.OO', '...', 'XXX'), ('OOO', '.XX', '..X'),
           ('XXX', 'O.X', 'O.O'), ('XOO', 'XX.', '.OX'), ('.XX', 'OXO', '.XO'), ('O..', 'XOO', 'XXX'),
           ('O..', 'OOX', 'XXX'), ('OXX', 'OO.', 'OXX'), ('O..', 'XO.', 'XXO'), ('.OX', '.XO', 'X..'),
           ('X.O', '.OX', 'O.X'), ('XXX', '.OO', 'X.O'), ('OOO', 'OXX', 'X.X'), ('XO.', '.XO', '..X'),
           ('XOO', 'X.X', 'XO.'), ('XXO', 'OXX', 'OXO'), ('XXO', '.XX', 'OOO'), ('O.X', 'XXX', '.OO'),
           ('OX.', '.OX', '.XO'), ('XX.', '.X.', 'OOO'), ('O.X', '.OX', 'OXX'), ('OOO', '.X.', '.XX'),
           ('..O', '.XO', 'XXO'), ('XO.', 'X..', 'XO.'), ('X.O', 'OX.', 'OXX'), ('OXX', '.O.', 'X.O'),
           ('.X.', 'OXO', '.X.'), ('XXX', 'OXO', 'O..'), ('XOO', 'XOX', 'X..'), ('XOO', '.X.', '..X'),
           ('.XO', 'XOX', 'OXO'), ('OOO', '.XX', 'XOX'), ('OX.', 'OXX', '.XO'), ('XX.', 'OOO', '.X.'),
           ('.OO', 'XXX', '.OX'), ('XXX', 'O..', '..O'), ('OX.', '.OO', 'XXX'), ('XOX', 'XOO', '.OX'),
           ('X.X', 'OOO', 'XOX'), ('OXO', 'OXX', '.X.'), ('XXO', 'OOO', 'X.X'), ('XXO', '.OO', 'OXX'),
           ('XOO', 'XOX', 'OX.'), ('.OX', '.OX', 'OXX'), ('XX.', 'XO.', 'XOO'), ('OXX', 'XOX', 'O.O'),
           ('XXX', 'O.X', 'OO.'), ('X.O', '.XX', 'OOX'), ('XX.', 'OOO', 'XXO'), ('X.X', '.OX', 'OOX'),
           ('.X.', 'OOO', 'X.X'), ('XXX', 'OO.', 'OX.'), ('OX.', 'O.O', 'XXX'), ('XXX', '..O', 'O..'),
           ('O.X', 'OX.', 'O.X'), ('OXX', 'OX.', 'X.O'), ('OOX', 'OXX', 'X..'), ('..O', 'XXX', '.O.'),
           ('..O', 'XXX', 'OOX'), ('..O', 'XXX', 'XOO'), ('.OO', 'XXX', '.XO'), ('OOX', '..X', 'OXX'),
           ('XOX', 'OXO', '..X'), ('XOX', 'OOO', 'XX.'), ('XXO', 'XO.', 'X.O'), ('X.O', 'XO.', 'X..'),
           ('OOO', 'XX.', 'X..'), ('.XO', 'XOO', 'XXO'), ('XXX', '.O.', 'O..'), ('OOO', '.XX', 'XXO'),
           ('OXX', '.XX', 'OOO'), ('XO.', '.XO', 'XOX'), ('X.O', 'XOX', 'XO.'), ('XOO', 'XXO', 'OXX'),
           ('OOX', 'XXO', 'OXX'), ('..X', '.XO', 'XO.'), ('X.X', 'OOO', 'X..'), ('XOO', '.XO', 'X.X'),
           ('OOX', '.XO', 'X.X'), ('XOX', 'OXO', 'X..'), ('.OX', '.X.', 'X.O'), ('XOX', 'OX.', 'X.O'),
           ('OO.', 'XXX', '.XO'), ('XX.', 'OXO', 'OX.'), ('XOX', 'OOX', '..X'), ('OOO', '.XX', 'X..'),
           ('OXX', 'OX.', '.XO'), ('.XO', 'XXO', 'OX.'), ('XOO', 'OXX', '..X'), ('OOX', 'OXX', '..X'),
           ('XX.', 'OOO', 'XOX'), ('O.X', 'OXX', '.OX'), ('.XX', '.XO', 'OXO'), ('OOO', '.XX', '.X.'),
           ('XOX', 'XO.', '.O.'), ('XXX', 'OO.', '...'), ('OOO', 'X..', 'XX.'), ('OX.', 'OX.', 'O.X'),
           ('..O', 'XO.', 'OXX'), ('XOX', '.O.', '.OX'), ('OX.', 'XOX', '..O'), ('XXX', '.OX', '.OO'),
           ('O.O', 'XXX', '.XO'), ('.XO', '.OX', 'O.X'), ('OOX', 'OXO', 'XXX'), ('XOO', 'OXO', 'XXX'),
           ('.XX', '.XO', 'XOO'), ('O.X', '.X.', 'X.O'), ('OXX', '..X', 'OOX'), ('O.X', 'OX.', 'X..'),
           ('X.O', '.OO', 'XXX'), ('OX.', '.XO', 'OXX'), ('XXO', 'OX.', '.OX'), ('X.O', 'X.O', 'XOX'),
           ('XOX', '.OX', 'XOO'), ('OXO', 'XOX', 'X.O'), ('OXX', '.O.', '.XO'), ('OOX', 'XOX', '..X'),
           ('X.O', 'XO.', 'O.X'), ('O.O', 'XXX', 'O.X'), ('O.X', 'O..', 'OXX'), ('XOX', '.OX', 'O.X'),
           ('X.O', 'XO.', 'XXO'), ('OXX', 'XXO', 'OXO'), ('X..', 'XX.', 'OOO'), ('.X.', '.X.', 'OXO'),
           ('O.O', 'XXX', 'OX.'), ('XOO', 'XX.', 'O.X'), ('XO.', '.OO', 'XXX'), ('.X.', 'XXO', 'OXO'),
           ('O.X', 'OX.', 'XOX'), ('XOX', 'XOX', '.OO'), ('O.X', '.XX', 'OOX'), ('O.X', '.XX', 'XOO'),
           ('XO.', 'OX.', 'XOX'), ('OOX', 'O.X', 'X.X'), ('.XO', 'XXO', '..O'), ('.XO', '.OX', 'OX.'),
           ('.OX', 'XXO', 'X.O'), ('OO.', 'XOX', 'XXO'), ('XX.', 'OXO', '.XO'), ('XXX', '.XO', 'O.O'),
           ('XXO', '.OX', 'O..'), ('XOX', 'X.X', 'OOO'), ('X.O', '..O', 'XXO'), ('.OX', 'OOX', '.XX'),
           ('X.X', 'XOO', 'XO.'), ('XX.', 'OXO', 'O.X'), ('X..', 'X.O', 'X.O'), ('OOX', '.OX', 'X.X'),
           ('XOO', 'XXX', 'OXO'), ('OOX', 'XXX', 'OXO'), ('OO.', '.OX', 'XXX'), ('O.X', '.OX', 'XOX'),
           ('.OO', 'XXX', 'OX.'), ('..O', 'OXO', 'XXX'), ('XOX', 'XXO', 'OOX'), ('OO.', '...', 'XXX'),
           ('OXO', '.X.', 'XXO'), ('OOX', 'XOX', 'X.O'), ('XXO', 'OXO', 'XOX'), ('XOX', 'XXO', 'XOO'),
           ('X..', 'OXX', 'OOX'), ('XXX', 'X.O', 'OO.'), ('XXO', 'X.O', 'XO.'), ('X..', 'OOO', 'X.X'),
           ('.XO', 'XOX', 'O..'), ('XXX', 'OX.', '.OO'), ('X..', '.XX', 'OOO'), ('.XX', '.OX', 'OOX'),
           ('XOX', '..X', 'OOX'), ('X..', 'XXO', 'OOX'), ('X..', 'XXO', 'XOO'), ('O.O', 'OX.', 'XXX'),
           ('XO.', 'OX.', '..X'), ('OXO', 'OX.', '.XX'), ('X.O', '.XO', '.XO'), ('O.X', '.XO', 'X..'),
           ('O.X', '.OX', '..X'), ('XXO', 'XOO', 'X..'), ('XOO', 'XOX', 'O.X'), ('X..', 'OXO', 'XOX'),
           ('..O', '..O', 'XXX'), ('OXX', 'OX.', 'O..'), ('O.O', 'XO.', 'XXX'), ('.XO', 'X.O', 'X.O'),
           ('OXX', 'OOX', 'X.O'), ('OXX', 'XOO', 'X.O'), ('X.O', 'XOX', 'OXO'), ('XOX', 'XO.', 'X.O'),
           ('.O.', 'XOX', '.OX'), ('XOO', '.XX', 'O.X'), ('OOX', '.XX', 'O.X'), ('XXX', '.O.', 'OXO'),
           ('.XX', 'OOO', 'X..'), ('X.X', 'OXO', 'XO.'), ('OXX', 'XOX', 'OOX'), ('...', '.OO', 'XXX'),
           ('XXX', 'OXO', '..O'), ('.XX', 'OOO', '.X.'), ('XO.', '.X.', '.OX'), ('.X.', '.XO', '.XO'),
           ('XXO', 'XOX', 'OO.'), ('X..', '.XO', '.OX'), ('X.O', 'O.O', 'XXX'), ('OOO', 'X.X', '.X.'),
           ('OO.', 'XXX', '...'), ('X.X', '.X.', 'OOO'), ('XXO', '.XO', '..O'), ('.OO', 'OX.', 'XXX'),
           ('XXX', 'OO.', '.XO'), ('X.X', 'XO.', 'XOO'), ('XXX', '.XO', 'OO.'), ('.OX', 'XOO', 'XOX'),
           ('.OX', '.OO', 'XXX'), ('XOO', 'OXX', 'XOX'), ('OOX', 'OXX', 'XOX'), ('OOX', 'XOX', '.XO'),
           ('XXO', 'OOX', 'OX.'), ('XXO', 'XOO', 'OX.'), ('.XX', 'XOX', 'OOO'), ('.X.', 'XX.', 'OOO'),
           ('OXX', '.OX', '..O'), ('OXO', '.X.', 'OXX'), ('OXX', 'OXX', 'XOO'), ('XO.', 'X.O', 'XXO'),
           ('X.X', 'X.O', 'XOO'), ('.O.', 'XXX', 'OOX'), ('XO.', 'OX.', 'OXX'), ('.O.', 'O..', 'XXX'),
           ('.O.', 'XXX', 'XOO'), ('XO.', '.XX', 'OOX'), ('X..', 'OX.', '.OX'), ('OX.', 'OX.', '.X.'),
           ('O.X', 'OOX', 'X.X'), ('OX.', 'OO.', 'XXX'), ('XXX', '..O', '..O'), ('OOO', 'XX.', '..X'),
           ('.XO', 'OXX', 'OX.'), ('XO.', 'XOO', 'XX.'), ('O.X', '..X', '.OX'), ('XOX', '.OO', 'XOX'),
           ('OXO', 'OXX', 'XXO'), ('XOO', 'OXX', 'XXO'), ('OOX', 'OXX', 'XXO'), ('X.X', 'O.X', 'OOX'),
           ('XXX', 'XO.', 'OO.'), ('OOX', 'OX.', 'XX.'), ('.XO', 'OXX', '.XO'), ('O.X', '.OO', 'XXX'),
           ('..O', 'XXO', '.XO'), ('OOX', 'OXX', 'OX.'), ('XXO', 'XO.', 'OXO'), ('XXX', 'OXO', 'OOX'),
           ('XXX', 'OXO', 'XOO'), ('OOO', 'X.X', 'OXX'), ('XOO', 'XO.', 'XX.'), ('XOO', 'XXX', 'O..'),
           ('OOX', 'XXX', 'O..'), ('XXO', 'OXO', 'OXX'), ('OO.', 'X.O', 'XXX'), ('XOX', 'XXO', 'OXO'),
           ('XX.', '..X', 'OOO'), ('OOO', '..X', '.XX'), ('XXO', 'X.O', 'OXO'), ('.XO', 'XX.', 'OXO'),
           ('OX.', 'XXX', '.OO'), ('XOX', 'XOO', 'OXX'), ('XOX', 'OOX', 'OXX'), ('XXX', '..O', '.O.'),
           ('OXO', 'OXX', 'XOX'), ('X..', 'X.X', 'OOO'), ('.OX', 'OX.', 'X..'), ('XO.', 'XOX', 'OOX'),
           ('X.O', 'XXO', 'OXO'), ('X.O', '.O.', 'OXX')}
    while True:
        s = input()
        if s == 'end':
            break

        print('valid' if tuple([s[:3], s[3:6], s[6:9]]) in his else 'invalid')


# tictac3()

import collections


def kingpath():
    def adds(x, y, c):
        s = (x, y)
        if s in sgs and s not in his:
            todo.append([x, y, c + 1])
            his.add(s)

    startx, starty, endx, endy = map(int, input().split())  # need to minus one
    seg = int(input())
    sgs = set()
    for i in range(seg):
        row, s, e = map(int, input().split())
        for i1 in range(s, e + 1):
            sgs.add((row, i1))
    todo = collections.deque([[startx, starty, 0]])
    his = set()
    while todo:
        x, y, step = todo.popleft()
        if x == endx and y == endy:
            return step
        adds(x - 1, y, step)
        adds(x + 1, y, step)
        adds(x, y - 1, step)
        adds(x, y + 1, step)
        adds(x - 1, y - 1, step)
        adds(x + 1, y + 1, step)
        adds(x - 1, y + 1, step)
        adds(x + 1, y - 1, step)
    return -1


# print(kingpath())

def postin():
    buildings = int(input())
    l = []
    c = 0
    for _ in range(buildings):
        d, h = map(int, input().split())
        while l and l[-1] > h:
            l.pop()
        if l and l[-1] != h or not l:
            c += 1
            l.append(h)
    return c


# print(postin())
import collections


def q1():
    for _ in range(int(input())):
        num = int(input())
        c = sorted(list(collections.Counter(input().split()).items()), key=lambda x: int(x[0]))
        ans = []
        for i in range(len(c)):
            ans.append(c[i][0])
            c[i] = [c[i][0]] + [c[i][1] - 1]
        for i in c:
            if i[1]:
                ans += i[1] * [i[0]]
        print(*ans, sep=' ')


# q1()

def q2():
    for _ in range(int(input())):
        num, m = map(int, input().split())
        now, *l = input().split()
        c = 1
        num -= 1
        while l:
            now = int(now)
            for i in range(num):
                if not (now + int(l[i])) % m:
                    now = l.pop(i)
                    break
            else:
                c += 1
                now, *l = l
            num -= 1
        print(c)


# q2()

def q2re():
    for _ in range(int(input())):
        counter = collections.defaultdict(int)
        num, m = map(int, input().split())
        ans = 0
        for i in input().split():
            counter[int(i) % m] += 1
        if counter[0]:
            ans += 1
        his = set()
        for i in list(counter.keys()):
            if i and i not in his:
                his.add(m - i)
                ans += 1
                ans += max(0, abs(counter[i] - counter[m - i]) - 1)

        print(ans)


# q2re()

def c1(num):
    if num % 2:
        return [1, num // 2, num // 2]
    else:
        half = num // 2
        if half % 2:
            return [2, half - 1, half - 1]
        else:
            return [half // 2, half // 2, half]


def c1call():
    for _ in range(int(input())):
        print(*c1(int(input().split()[0])), sep=' ')


# c1call()


def c2call():
    for _ in range(int(input())):
        num, k = map(int, input().split())
        print(*[1] * (k - 3), *c1(num - (k - 3)), sep=' ')


# c2call()


def dominos():
    for _ in range(int(input())):
        n, k, k1 = map(int, input().split())
        w, b = map(int, input().split())
        if k1 > k:
            r = k1 - k
            w -= k
            w -= (r // 2)
            br = n - k - (n - k1)
            b -= (n - k1)
            b -= (br // 2)
        elif k1 < k:
            r = k - k1
            w -= k1
            w -= (r // 2)
            br = n - k1 - (n - k)
            b -= (n - k)
            b -= (br // 2)
        else:
            w -= k1
            b -= (n - k)
        print('yes' if b <= 0 and w <= 0 else 'no')
# dominos()



def biremove():
    for _ in range(int(input())):
        s = input()
        if ''.join(sorted(s)) == s:
            print('yes')
        else:
            # pos = 0
            for i in range(len(s)-1):
                if s[i] == '1' and s[i+1] =='1':
                    pos = i
                    break
            else:
                print('yes')
                continue
            for i in range(pos+1,len(s)-1):
                if s[i] == '0' and s[i+1] == '0':
                    break
            else:
                print('yes')
                continue
            print('no')
biremove()