BlueBook

Given ~T~ ~(1 \le T \le 10\,000)~ non-negative year values, where each year ~Y~ is ~0 \le Y \le 1\,000\,000~, determine whether or not each one is a leap year.

Remember: A year is a leap year if it is divisible by ~4~ but not by ~100~ or if it is divisible by ~400~. ~0~ is considered a leap year.

Input Specification

Line ~1~: A single integer representing the number of test cases (years to be entered)
Next ~T~ lines: Each year value

Output Specification

Lines ~1 \dots T~: one integer 1 or 0 denoting whether ~N~ is a leap year. Output 1 if ~N~ is a leap year, and 0 otherwise.

Sample Input

4
0
4
100
400

Sample Output

1
1
0
1