The Hendrie Sequence “H” is a self-describing sequence defined as follows: • H(1)=0 • If we expand every number x in H to a subsequence containing x 0’s followed by the number x+1, the resulting sequence is still H (without its first element). 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