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 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. Binary representation of 13 is 1101. 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 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 a bit that needs to be added to form an even parity.

0
1
2
3
4
		        

0
1
1
0
1