Given a non-negative number represented as a linked list, determine whether it is a palindrome or not.

Example 1:

Number : 1234
Linked list : 1→2→3→4
Result : Not a palindrome

Example 2:

Number : 1221
Linked list : 1→2→2→1
Result : A palindrome

Testing

Input Format

The first line contains ‘T’, denoting the number of test cases.

For each test case the input has two lines:

• A number ‘n’, denoting the length of the number.
• n space-separated integers, denoting digits of the number.

Output Format

For each test case, the output has one line with 1 if the number is a palindrome, 0 otherwise.

Sample Input

4
4
3 4 5 3
5
1 2 3 2 1
3
3 1 3
4
1 4 4 1

Expected Output

0
1
1
1

Constraints

1 <= T <= 100
1 <= n <= 104
0 <= nodeValue <= 9