String Transformation Solution

Page Contents

String Transformation

You are given a string SS of length NN contains only 1,2,31,2,3 as a character. You have to replace every similar character with either an open bracket or close bracket so that the newly formed string is a balanced bracket sequence. For ex : str = “1123” (take 11 as ‘(‘ ‘2’ as ‘)’ and 33 as ‘)’ then formed string will look like “(())”) and “121232” can be transformed to balance bracket sequence while “1121” and “11” can not.

Your task is to determine if it is possible to transform a given string to a balanced bracket sequence or not.

Input Format

The first line contains a single integer TT – the number of test cases. The first and only line of each test case consists of a string SS.

Output Format

Print “YES” if it is possible to transform a given string to a balanced bracket sequence else print “NO”.

Constraints

1≤T≤1031≤T≤103 1≤|S|≤1051≤|S|≤105 S will only contain 1,2,31,2,3 character. |S| is length of the string

Time Limit

1 second

Example

Sample Input

3 1123 121232 1121

Sample Output

YES YES NO

Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.