A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction. Example words: rotator, racecar, level, radar, ... etc. More information on palindromes can be found on Wikipedia, http://en.wikipedia.org/wiki/Palindrome. A typical application of the Stacks and Queues is to detect Palindromes, by pushing the string to be tested in a stack and enqueuing it in a queue character by character. Then, it is possible to detect whether the string under test is a Palindrome or not by popping it from the stack and dequeuing it from the queue and comparing the output characters.

In this problem you will implement a simple palindrome detection using stacks and queues, either static or dynamic. It is obligatory to use at least one stack and one queue in your problem. Failing to meet this requirement will result in your answer being disqualified and rejected.

Input

The input consists of N test cases. The first line of the input contains only the positive number N. There are exactly N lines of input following the first line. Each of those lines contains exactly one string to be tested for being a palindrome. The test strings are guaranteed to be free of all white spaces. Also, the test strings are guaranteed to be less than 50 characters in length, excluding the null-terminating character.

Output

For each test string, print exactly one line containing exactly one number. This number should be 1 if the test string is a palindrome and should be 0 if the test string is not a palindrome.

Example

Input:
5
radar
exam
wysiwyg
level
rotator


Output:
1
0
0
1
1