Hendrie Sequence 

The Hendrie Sequence ``H" is a self-describing sequence defined as follows:

Thus, the first few elements of H are:


0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,...


You must write a program that, given n, calculates the nth element of H.

Input 

Each test case consists of a single line containing the integer n ( 0 < n < 263) . Input is terminated with a line containing the number `0' which of course should not be processed.

Output 

For each test case, output the nth element of H on a single line.

Sample Input 

4
7
44
806856837013209088
0

Sample Output 

2
0
3
16



Problem setter: Derek Kisman, University of Waterloo, Canada