시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 122 49 40 52.632%

문제

완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수이다. 예를 들어, 6의 약수는 1, 2, 3인데 1+2+3은 6이기 때문에 완전수이고, 28도 1+2+4+7+14 = 28이기 때문에 완전수이다.

어떤 자연수의 나쁨이란 자기 자신을 제외한 약수의 합과 자기 자신과의 차이이다.

꽤 좋은 수는 자연수의 나쁨이 어떤 특정한 값보다 크지 않은 수이다. 예를 들어, 나쁨을 2까지 허용한다면, 100보다 작은 수 중에 꽤 좋은 수는 11가지 2, 3, 4, 6, 8, 10, 16, 20, 28, 32, 64)가 있다. 이 나쁨의 기준을 0으로 바꿔버리면 완전수의 정의와 같아진다.

허용하는 나쁨의 최대값이 주어졌을 때, 꽤 좋은 수가 입력으로 주어지는 구간 안에 몇 개 있는지 구하는 프로그램을 작성하시오. 

입력

입력은 테스트 케이승 여러개로 이루어져 있다. 각 테스트 케이스는 한 줄이고 start stop badness 세 정수를 포함한다.

  • start (2 ≤ start < 1000000)
  • stop (start ≤ stop < 1000000)
  • badness (0 ≤ badness < 1000)

입력의 마지막 줄에는 0이 세 개 주어진다. 

출력

각 테스트 케이스에 대해서, 입력으로 주어진 구간에 포함되는 자연수 중 꽤 좋은 수의 개수를 출력한다. (start와 stop도 구간에 포함되고, 나쁨의 최대값은 badness로 주어진다)

예제 입력 1

2 100 2
2 100 0
1000 9999 3
0 0 0

예제 출력 1

Test 1: 11
Test 2: 2
Test 3: 6
W3sicHJvYmxlbV9pZCI6IjkyMTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmNjQgXHVjODhiXHVjNzQwIFx1YzIyYlx1Yzc5MCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNjQ0XHVjODA0XHVjMjE4XHViMjk0IFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTVjIFx1YzU3ZFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWI0MThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA2XHVjNzU4IFx1YzU3ZFx1YzIxOFx1YjI5NCAxLCAyLCAzXHVjNzc4XHViMzcwIDErMiszXHVjNzQwIDZcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzY0NFx1YzgwNFx1YzIxOFx1Yzc3NFx1YWNlMCwgMjhcdWIzYzQgMSsyKzQrNysxNCA9IDI4XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM2NDRcdWM4MDRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NTggXHViMDk4XHVjMDY4XHVjNzc0XHViNzgwIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTVjIFx1YzU3ZFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWFjZmMgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YWNmY1x1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWY2NCBcdWM4OGJcdWM3NDAgXHVjMjE4XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWIwOThcdWMwNjhcdWM3NzQgXHVjNWI0XHViNWE0IFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWFjMTJcdWJjZjRcdWIyZTQgXHVkMDZjXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjA5OFx1YzA2OFx1Yzc0NCAyXHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNFx1YmE3NCwgMTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWMyMTggXHVjOTExXHVjNWQwIFx1YWY2NCBcdWM4OGJcdWM3NDAgXHVjMjE4XHViMjk0IDExXHVhYzAwXHVjOWMwIDIsIDMsIDQsIDYsIDgsIDEwLCAxNiwgMjAsIDI4LCAzMiwgNjQpXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjA5OFx1YzA2OFx1Yzc1OCBcdWFlMzBcdWM5MDBcdWM3NDQgMFx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmZDRcdWJjODRcdWI5YWNcdWJhNzQgXHVjNjQ0XHVjODA0XHVjMjE4XHVjNzU4IFx1YzgxNVx1Yzc1OFx1YzY0MCBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDVjOFx1YzZhOVx1ZDU1OFx1YjI5NCBcdWIwOThcdWMwNjhcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWY2NCBcdWM4OGJcdWM3NDAgXHVjMjE4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZDZjXHVhYzA0IFx1YzU0OFx1YzVkMCBcdWJhODcgXHVhYzFjIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmI5IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNzc0XHVhY2UwIHN0YXJ0IHN0b3AgYmFkbmVzcyBcdWMxMzggXHVjODE1XHVjMjE4XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5zdGFydCAoMiAmbGU7IHN0YXJ0ICZsdDsgMTAwMDAwMCk8XC9saT5cclxuXHQ8bGk+c3RvcCAoc3RhcnQgJmxlOyBzdG9wICZsdDsgMTAwMDAwMCk8XC9saT5cclxuXHQ8bGk+YmFkbmVzcyAoMCAmbGU7IGJhZG5lc3MgJmx0OyAxMDAwKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjMTM4IFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IFx1YzkxMSBcdWFmNjQgXHVjODhiXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoc3RhcnRcdWM2NDAgc3RvcFx1YjNjNCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVhY2UwLCBcdWIwOThcdWMwNjhcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQwIGJhZG5lc3NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkyMTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJRdWl0ZSBHb29kIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgJnF1b3Q7cGVyZmVjdCZxdW90OyBudW1iZXIgaXMgYW4gaW50ZWdlciB0aGF0IGlzIGVxdWFsIHRvIHRoZSBzdW0gb2YgaXRzIGRpdmlzb3JzICh3aGVyZSAxIGlzIGNvbnNpZGVyZWQgYSBkaXZpc29yKS4gRm9yIGV4YW1wbGUsIDYgaXMgcGVyZmVjdCBiZWNhdXNlIGl0cyBkaXZpc29ycyBhcmUgMSwgMiwgYW5kIDMsIGFuZCAxICsgMiArIDMgaXMgNi4gU2ltaWxhcmx5LCAyOCBpcyBwZXJmZWN0IGJlY2F1c2UgaXQgZXF1YWxzIDEgKyAyICsgNCArIDcgKyAxNC48XC9wPlxyXG5cclxuPHA+QSAmcXVvdDtxdWl0ZSBnb29kJnF1b3Q7IG51bWJlciBpcyBhbiBpbnRlZ2VyIHdob3NlICZxdW90O2JhZG5lc3MmcXVvdDsgJm5kYXNoOyB0aGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgc3VtIG9mIGl0cyBkaXZpc29ycyBhbmQgdGhlIG51bWJlciBpdHNlbGYgJm5kYXNoOyBpcyBub3QgZ3JlYXRlciB0aGFuIGEgc3BlY2lcdWZiMDFlZCB2YWx1ZS4gRm9yIGV4YW1wbGUsIGlmIHRoZSBhbGxvd2FibGUgYmFkbmVzcyBpcyBzZXQgYXQgMiwgdGhlcmUgYXJlIDExICZxdW90O3F1aXRlIGdvb2QmcXVvdDsgbnVtYmVycyBsZXNzIHRoYW4gMTAwOiAyLCAzLCA0LCA2LCA4LCAxMCwgMTYsIDIwLCAyOCwgMzIsIGFuZCA2NC4gQnV0IGlmIHRoZSBhbGxvd2FibGUgYmFkbmVzcyBpcyBzZXQgYXQgMCAoY29ycmVzcG9uZGluZyB0byB0aGUgJnF1b3Q7cGVyZmVjdCZxdW90OyBudW1iZXJzKSB0aGVyZSBhcmUgb25seSAyOiA2IGFuZCAyOC48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjb3VudCBob3cgbWFueSBxdWl0ZSBnb29kIG51bWJlcnMgKG9mIGEgc3BlY2lcdWZiMDFlZCBtYXhpbXVtIGJhZG5lc3MpIGZhbGwgaW4gYSBzcGVjaVx1ZmIwMWVkIHJhbmdlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIHNwZWNpXHVmYjAxY2F0aW9ucyBmb3IgYSBzZXJpZXMgb2YgdGVzdHMuIEluZm9ybWF0aW9uIGZvciBlYWNoIHRlc3QgaXMgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIDMgaW50ZWdlcnMgd2l0aCBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIGl0ZW1zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnN0YXJ0ICgyICZsdDs9IHN0YXJ0ICZsdDsgMTAwMDAwMCkgc3BlY2lcdWZiMDFlcyB0aGUgXHVmYjAxcnN0IG51bWJlciB0byB0ZXN0PFwvbGk+XHJcblx0PGxpPnN0b3AgKHN0YXJ0ICZsdDs9IHN0b3AgJmx0OyAxMDAwMDAwKSBzcGVjaVx1ZmIwMWVzIHRoZSBsYXN0IG51bWJlciB0byB0ZXN0PFwvbGk+XHJcblx0PGxpPmJhZG5lc3MgKDAgJmx0Oz0gYmFkbmVzcyAmbHQ7IDEwMDApIHNwZWNpXHVmYjAxZXMgdGhlIG1heGltdW0gYWxsb3dhYmxlIGJhZG5lc3M8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIGxpbmUgY29udGFpbmluZyAzIHplcm9zIHRlcm1pbmF0ZXMgdGhlIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBzaG91bGQgY29uc2lzdCBvZiBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNvbXByaXNpbmcgdGhlIHRlc3QgbnVtYmVyIChmb3JtYXR0ZWQgYXMgc2hvd24pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgbnVtYmVyIG9mIHZhbHVlcyBpbiB0aGUgdGVzdCByYW5nZSB3aXRoIGJhZG5lc3Mgbm90IGdyZWF0ZXIgdGhhbiB0aGUgYWxsb3dhYmxlIHZhbHVlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==