NINJA’S STRING

Ninja developed his own coding platform and he wants all the questions of string to be uploaded on his platform. So he wants to create test cases of the string but as usual, he uses his own ninja technique for selecting the strings and calls such strings as ninja strings. A valid ninja string must contain at least three numbers and except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

So help our ninja to write the code so he is able to check whether the string is a ninja string or not.

So your task is to write a code for a given string containing only digits ‘0 - 9’ for determining whether the string is a ninja string or not.

Example :

‘1123’ is a ninja string, since ‘1 + 1 = 2’ and ‘1 + 2 = 3’. 

Note :

Numbers in the ninja string cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a string ‘S’, representing the string for which you have to determine if this string is a ninja string or not.

Output Format :

For each test case, print a single line as ‘True’ or ‘False’  as per the given condition.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function. 

Constraints :

1 <= T <= 5
1 <= |S| <= 30  

Where ‘T’ represents the number of test cases and ‘S’ represents the given string.

Time Limit: 1 second  

Sample Input 1 :

2
112358
2356

Sample Output 1 :

True
False

Explanation Of Sample Input 1 :

Test Case 1:
In the first line, there is the number of test cases i.e., ‘2’, and in the next line ‘112358’ is the given string so now we look for our condition 
‘1 + 1 = 2’
‘1 + 2 = 3’
‘2 + 3 = 5’
‘3 + 5 = 8’
Hence we return ‘True’ as it satisfies the given condition for the ninja string.

Test Case 2:
For this test case given string is ‘2356’ 
‘2 + 3 = 5’
But ‘3 + 5 = 8’ but in string ‘6’ is present so we return ‘False’ as it doesn’t satisfy the given condition for the ninja string.

Sample Input 2 :

1
235813

Sample Output 2 :

True

Explanation Of Sample Input 2 :

Test Case 1:
In the first line, there is the number of test cases i.e., ‘1’, and in the next line ‘235813’ is the given string so now we look for our condition 
‘2 + 3 = 5’
‘3 + 5 = 8’
‘5 + 8 = 13’
Hence we return ‘True’ as it satisfies the given condition for the ninja string.