시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 67 4 4 44.444%

문제

0보다 큰 정수 N0이 주어졌을 때, N1을 N0을 이진수로 나타냈을 때, 1의 개수라고 하자. N0 = 27인 경우, N1 = 4가 된다.

0보다 큰 모든 i에 대해서, Ni를 Ni-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 ≤ 1018, 0 ≤ X ≤ 10) 입력의 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스에 대해서, LO부터 HI를 포함하는 범위 내의 정수를 N0으로 했을 때, K값이 X가 되는 것의 개수를 출력한다.

예제 입력 1

31 31 3
31 31 1
27 31 1
27 31 2
1023 1025 1
1023 1025 2
0 0 0

예제 출력 1

1
0
0
3
1
1
W3sicHJvYmxlbV9pZCI6IjQwOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWQyYjggXHVhYzFjXHVjMjE4IFx1YzEzOFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0MFx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjODE1XHVjMjE4IE48c3ViPjA8XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE48c3ViPjE8XC9zdWI+XHVjNzQ0IE48c3ViPjA8XC9zdWI+XHVjNzQ0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYzhcdWM3NDQgXHViNTRjLCAxXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIE48c3ViPjA8XC9zdWI+ID0gMjdcdWM3NzggXHVhY2JkXHVjNmIwLCBOPHN1Yj4xPFwvc3ViPiA9IDRcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQwXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWJhYThcdWI0ZTAgaVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIE48c3ViPmk8XC9zdWI+XHViOTdjIE48c3ViPmktMTxcL3N1Yj5cdWM3NDQgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1Yzc0NCBcdWI1NGMsIDFcdWM3NTggXHVhYzFjXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgMVx1YzczY1x1Yjg1YyBcdWMyMThcdWI4MzRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdE48c3ViPjA8XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIEtcdWI5N2MgTjxzdWI+aTxcL3N1Yj49MVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgaVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBOPHN1Yj4wPFwvc3ViPj0zMVx1Yzc3OCBcdWFjYmRcdWM2YjAsIE48c3ViPjE8XC9zdWI+PTUsIE48c3ViPjI8XC9zdWI+PTIsIE48c3ViPjM8XC9zdWI+PTFcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIEs9M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNWYwXHVjMThkXHViNDFjIFx1YmM5NFx1YzcwNFx1YzY0MCBcdWM1YjRcdWI1YTQgXHVjMjE4IFhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYzk0XHVjNzA0IFx1YzU0OFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhYzAxXHVhYzAxIE48c3ViPjA8XC9zdWI+XHVjNzNjXHViODVjIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIEtcdWFjMTJcdWM3NzQgWFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YmE4NyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYzk0XHVjNzA0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBMT1x1YzY0MCBISSBcdWFkZjhcdWI5YWNcdWFjZTAgWFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTE8gJmxlOyBISSAmbGU7IDEwPHN1cD4xODxcL3N1cD4sIDAgJmxlOyBYICZsZTsgMTApIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgM1x1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBMT1x1YmQ4MFx1ZDEzMCBISVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHViYzk0XHVjNzA0IFx1YjBiNFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgTjxzdWI+MDxcL3N1Yj5cdWM3M2NcdWI4NWMgXHVkNTg4XHVjNzQ0IFx1YjU0YywgS1x1YWMxMlx1Yzc3NCBYXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MDkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQml0IENvdW50aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5TdGFydCB3aXRoIGFuIGludGVnZXIsIE48c3ViPjA8XC9zdWI+LCB3aGljaCBpcyBncmVhdGVyIHRoYW4gMC4gTGV0IE48c3ViPjE8XC9zdWI+IGJlIHRoZSBudW1iZXIgb2Ygb25lcyBpbiB0aGUgYmluYXJ5IHJlcHJlc2VudGF0aW9uIG9mIE48c3ViPjA8XC9zdWI+LiBTbywgaWYgTjxzdWI+MDxcL3N1Yj49MjcsIE48c3ViPjE8XC9zdWI+PTQuIEZvciBhbGwgaSZndDswLCBsZXQgTjxzdWI+aTxcL3N1Yj4gYmUgdGhlIG51bWJlciBvZiBvbmVzIGluIHRoZSBiaW5hcnkgcmVwcmVzZW50YXRpb24gb2YgTjxzdWI+aS0xPFwvc3ViPi4gVGhpcyBzZXF1ZW5jZSB3aWxsIGFsd2F5cyBjb252ZXJnZSB0byBvbmUuIEZvciBhbnkgc3RhcnRpbmcgbnVtYmVyLCBOPHN1Yj4wPFwvc3ViPiwgbGV0IEsgYmUgdGhlIG1pbmltdW0gdmFsdWUgb2YgaSZndDs9MCBmb3Igd2hpY2ggTjxzdWI+aTxcL3N1Yj49MS4gRm9yIGV4YW1wbGUsIGlmIE48c3ViPjA8XC9zdWI+PTMxLCB0aGVuIE48c3ViPjE8XC9zdWI+PTUsIE48c3ViPjI8XC9zdWI+PTIsIE48c3ViPjM8XC9zdWI+PTEsIHNvIEs9My48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSByYW5nZSBvZiBjb25zZWN1dGl2ZSBudW1iZXJzLCBhbmQgYSB2YWx1ZSBYLCBob3cgbWFueSBudW1iZXJzIGluIHRoZSByYW5nZSBoYXZlIGEgSyB2YWx1ZSBlcXVhbCB0byBYPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgdGhyZWUgaW50ZWdlcnMgb24gYSBzaW5nbGUgbGluZTo8XC9wPlxyXG5cclxuPHA+TE8gSEkgWDxcL3A+XHJcblxyXG48cD5XaGVyZSBMTyBhbmQgSEkgKDEgJmxlOyBMTyAmbGU7IEhJICZsZTsgMTAxOCkgYXJlIHRoZSBsb3dlciBhbmQgdXBwZXIgbGltaXRzIG9mIGEgcmFuZ2Ugb2YgaW50ZWdlcnMsIGFuZCBYICgwICZsZTsgWCAmbGU7IDEwKSBpcyB0aGUgdGFyZ2V0IHZhbHVlIGZvciBLLiBUaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCB0aHJlZSAwcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgcmFuZ2UgZnJvbSBMTyB0byBISSAoaW5jbHVzaXZlKSB3aGljaCBoYXZlIGEgSyB2YWx1ZSBlcXVhbCB0byBYIGluIHRoZSBpbnB1dC4gUHJpbnQgZWFjaCBpbnRlZ2VyIG9uIGl0cyBvd24gbGluZSB3aXRoIG5vIHNwYWNlcy4gRG8gbm90IHByaW50IGFueSBibGFuayBsaW5lcyBiZXR3ZWVuIGFuc3dlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d