A **parity bit** is a binary digit that is added to ensure that the number of bits with value of 1 in a given set of bits is always even or odd. Parity bits are used as a simple validation code, for example to test that all the data has arrived correctly in a transmission. For this question we’ll be using an *even parity bit scheme* – that is, we want to append a bit (1 or 0) so that the total number of high bits (1) is *even*.

For example, consider the integer 13. The binary representation of 13 is 1101. The number of high bits in 1101 is 3, which is odd. To make it even, the parity bit must also be high, so 1 is added to the bit string to form 11011.

The input file **DATA3.txt** will contain 5 lines, integers 0 ≤ `N` ≤ 128.

The output file **OUT3.txt** will contain 5 lines – a single integer, 1 or 0, representing the bit that needs to be added to form an even parity.

```
0
1
2
3
4
```

```
0
1
1
0
1
```