BlueBook

Given $T$ $(1\le T\le 10000)$ non-negative year values, where each year $Y$ is $0\le Y\le 1000000$, 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