1이 될 때까지

$N_0 > 0$인 정수에서 시작합니다. $N_1$을 $N_0$의 이진 표현에 들어 있는 1의 개수로 정의합니다. 예를 들어 $N_0 = 27$이면 $N_1 = 4$입니다.

일반적으로 $N_i$는 $N_{i-1}$의 이진 표현에 들어 있는 1의 개수입니다. 이 수열은 항상 1로 수렴합니다.

임의의 시작 수 $N_0$에 대해, $K(N_0)$을 $N_i = 1$이 되는 가장 작은 첨자 $i$로 정의합니다. 예를 들어 $N_0 = 31$이면 $N_1 = 5$, $N_2 = 2$, $N_3 = 1$이므로 $K(31) = 3$입니다. 특히 $N_0 = 1$은 이미 1이므로 $K(1) = 0$입니다.

연속한 정수 구간과 값 $X$가 주어졌을 때, 구간 안에서 $K(\ldots)$ 값이 $X$와 같은 수는 몇 개일까요?

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 세 정수가 한 줄에 주어집니다.

LO HI X

여기서 $LO$와 $HI$ ($1 \le LO \le HI \le 10^{18}$)는 정수 구간의 하한과 상한이고, $X$ ($0 \le X \le 10$)는 $K(\ldots)$의 목표 값입니다.

입력의 끝은 세 개의 0으로 이루어진 줄이며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다, 구간 $[LO, HI]$(양 끝 포함) 안에서 $K(\ldots)$ 값이 $X$와 같은 정수의 개수를 한 줄에 하나의 정수로 출력합니다.