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 ~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 even parity bit – that is, we want to add a bit (~1~ or ~0~) so that the total number of high bits (~1~) is even.

For example, consider 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~.

The input will contain 5 lines, integers ~0 \le N \le 128~.

The output will contain 5 lines – a single integer, ~1~ or ~0~, 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