비트 개수 세기

양의 정수 N0에 대해, N1을 N0을 이진수로 나타냈을 때 나오는 1의 개수라고 하자. 예를 들어 N0 = 27(이진수로 11011)인 경우 N1 = 4이다.

0보다 큰 모든 i에 대해, Ni를 바로 이전 항 N(i-1)을 이진수로 나타냈을 때 나오는 1의 개수라고 하자. 이 수열은 항상 1로 수렴한다.

N0이 주어졌을 때, K를 Ni = 1을 만족하는 가장 작은 i라고 하자. 예를 들어 N0 = 31인 경우 N1 = 5, N2 = 2, N3 = 1이므로 K = 3이다.

연속된 범위와 정수 X가 주어졌을 때, 그 범위 안의 각 정수를 N0으로 삼았을 때 K값이 X가 되는 경우가 몇 가지인지 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 한 줄이다. 각 줄에는 범위의 양 끝인 LO와 HI, 그리고 X가 주어진다 (1 ≤ LO ≤ HI ≤ 10^18, 0 ≤ X ≤ 10). 입력의 마지막 줄에는 0이 세 개 주어진다.

각 테스트 케이스에 대해, LO부터 HI까지(양 끝 포함)의 정수를 N0으로 삼았을 때 K값이 X가 되는 것의 개수를 출력한다.