## Problem: Permutation divisibility

You are given a number. Your task is to check if there exists a permutation of the digits of this number which is divisible by 4.

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of one line. The line consists of a non negative integer N. This integer may have leading zeros.

Output:
Corresponding to each test case, in a new line, print 1 if such a permutation of this number exists or print 0 if such a permutation doesn’t exist.
Constraints:

1 ≤ T ≤ 100

0 ≤ N ≤ 10200
Example:

Input

3
003
715
123456

Output

1
0
1

Explanation:
For 003, we have a permutation 300 which is divisible by 4.
For 123456, we have 123564 which is a permutation of 123456 and is divisible by 4.

In order to solve this problem, you must know that a number is divisible by 4 if it is 0, 4, 8 , or its last two digits divisible by 4.

Python 2.7:

```from itertools import *
if __name__ == '__main__':
dic = set()
for _ in range(0, 96+1, 4):
if _ < 10:
else:

t = input()
for _ in range(t):
n = raw_input()
#print n
if int(n) == 0 or int(n) == 4 \
or int(n) == 8:
print 1
else:
for (a,b) in list(permutations(n, 2)):
if  ''.join((a, b)) in dic \
or ''.join((b, a)) in dic:
print 1
break
else:
print 0

```