The chef is very expert in coding, so to keep his password safe from the hackers. He always enters a decoded code of his password. You are a hacker and your work is to find the maximum number of possible ways to unlock his password in encoded form.

The encoded message containing only letters from A-Z is being encoded with numbers using the following mapping: 

'A' -> 1 

'B' -> 2 ... 

'Z' -> 26

You have given a non-empty string containing only digits, determine the total number of ways to encode it. 

If the total number of ways are even then you are able to unlock the password. 

Input: 
The first line has a single integer T, denoting the number of test cases. The first line of each test case contains string “S” decoded number.

Output:
For each test case, in a new line, print 'YES' if number of maximum ways are even, otherwise
'NO'. (without quotes)

Constraints:
1 ≤ T ≤ 50

1 ≤ S ≤ 30

Sample Input:
2

12

223

Sample Output:
YES

NO

Explanation:
For first test case, It could be encoded as "AB" (1 2) or "L" (12), hence the number of
maximum possible ways are 2 so output is “YES”.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
while t>0:
 s = input().strip()
 if not s:
  print('NO')

 dp = [0 for x in range(len(s) + 1)]
 dp[0] = 1
 dp[1] = 1 if 0 < int(s[0]) <= 9 else 0

 for i in range(2, len(s) + 1):
  if 0 < int(s[i-1:i]) <= 9:
   dp[i] += dp[i - 1]
  if s[i-2:i][0] != '0' and int(s[i-2:i]) <= 26:
   dp[i] += dp[i - 2]
 
 if dp[len(s)]%2 == 0:
  print('YES')
 else:
  print('NO')
 t -= 1

def numDecodings(A):
  if A[0]=='0':
   return 0
  d=[0]*(len(A)+1)
  d[0]=1
  d[1]=1
  for i in range(1,len(A)):
   g=int (A[i-1]+A[i])
   if A[i]=='0' and(g!=10 and g!=20) :
    return 0
   elif g==10 or g==20 :
    d[i+1]=d[i-1]
   elif g>10 and g<=26 :
    d[i+1]=d[i]+d[i-1]
   else : 
    d[i+1]=d[i]
  
 
  return d[len(A)];        

for _ in range (int(input())):
 digits = input()
 n = len(digits) 
 if(numDecodings(digits)%2==0):
  print("YES")
 else:
  print("NO")

def numDecodings(s):
 s = '10' + s
 dec = [1] * (len(s) + 2)

 for i in range(2, len(s)):
  # invalid case or '10, 20'
  if s[i] == '0':
   if s[i - 1] != '1' and s[i - 1] != '2':
    return 0
   dec[i] = dec[i - 2]
  # 1 - 9, 27 -
  elif int(s[i - 1: i + 1]) > 26 or int(s[i - 1: i + 1]) < 10:
   dec[i] = dec[i - 1]
   # 11 - 26 (except for 20)
  else:
   dec[i] = dec[i - 1] + dec[i - 2]

 return dec[len(s) - 1]

for _ in range(int(input()))    :
 nums = input()
 ways = numDecodings(nums)
 print(["NO", "YES"][ ways % 2 == 0])