Define f(n) for positive integers n by recurrence (1) f(1) = 1; (2) f(2*n) = f(n) (3) f(2n+1) = f(n)+f(n+1); The problem is given n, you should tell us whether it is an even number or an odd number.

The input consists of multiple test cases. Each test case contains 1 integer n (1 <= n <= 1000,000,000)

For each test case, if f(n) is an even number just output 0 otherwise 1 on a single line.