##### DWITE Online Computer Programming Contest, February 2008, Problem 3

A parity bit is a binary digit that is added to ensure that the number of bits with a value of 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 **even parity bit** – that is, we want to add a bit ( or ) so that the total number of high bits () is *even*.

For example, consider integer . The binary representation of is `1101`

. The number of high bits in `1101`

is , which is odd. To make it even, the parity bit must also be high, so .

The input will contain 5 lines, integers .

The output will contain 5 lines – a single integer, or , representing a bit that needs to be added to form an even parity.

#### Sample Input

```
0
1
2
3
4
```

#### Sample Output

```
0
1
1
0
1
```

Problem Resource: DWITE

## Comments