시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 757 103 69 13.503%

문제

1640년 12월 25일, 위대한 수학자 피에르 드 페르마는 마랭 메르센에게 다음과 같은 내용의 편지를 썼다.

I just proved that an odd prime p is expressible as p = a2 + b2 if and only if p is expressible as p = 4c + 1.

편지에는 증명은 포함되어 있지 않았고, 100년후에 오일러가 증명했다. 5, 13, 17, 41은 두 제곱수의 합으로 나타낼 수 있다.

5=22+11 13=32+22 17=42+12 41=52+42

하지만, 11, 19, 23, 31은 제곱수의 합으로 나타낼 수 없다.

어떤 구간이 주어졌을 때, 이 구간에 포함되어 있는 소수를 제곱수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L과 U가 공백으로 구분되어 주어진다. (L ≤ U < 1,000,000)

입력의 마지막 줄은 L과 U가 -1이다.

출력

각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 것의 개수이다.

예제 입력 1

10 20
11 19
100 1000
-1 -1

예제 출력 1

10 20 4 2
11 19 4 2
100 1000 143 69
W3sicHJvYmxlbV9pZCI6IjQ5MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzOThcdWI5NzRcdWI5YzhcdWM3NTggXHVkMDZjXHViOWFjXHVjMmE0XHViOWM4XHVjMmE0IFx1YzgxNVx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+MTY0MFx1YjE0NCAxMlx1YzZkNCAyNVx1Yzc3YywgXHVjNzA0XHViMzAwXHVkNTVjIFx1YzIxOFx1ZDU1OVx1Yzc5MCBcdWQ1M2NcdWM1ZDBcdWI5NzQgXHViNGRjIFx1ZDM5OFx1Yjk3NFx1YjljOFx1YjI5NCBcdWI5YzhcdWI3YWQgXHViYTU0XHViOTc0XHVjMTNjXHVjNWQwXHVhYzhjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViMGI0XHVjNmE5XHVjNzU4IFx1ZDNiOFx1YzljMFx1Yjk3YyBcdWMzN2NcdWIyZTQuPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPkkganVzdCBwcm92ZWQgdGhhdCBhbiBvZGQgcHJpbWUgcCBpcyBleHByZXNzaWJsZSBhcyBwID0gYTxzdXA+MjxcL3N1cD4gKyBiPHN1cD4yPFwvc3VwPiBpZiBhbmQgb25seSBpZiBwIGlzIGV4cHJlc3NpYmxlIGFzIHAgPSA0YyArIDEuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1ZDNiOFx1YzljMFx1YzVkMFx1YjI5NCBcdWM5OWRcdWJhODVcdWM3NDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM1NThcdWFjZTAsIDEwMFx1YjE0NFx1ZDZjNFx1YzVkMCBcdWM2MjRcdWM3N2NcdWI3ZWNcdWFjMDAgXHVjOTlkXHViYTg1XHVkNTg4XHViMmU0LiA1LCAxMywgMTcsIDQxXHVjNzQwIFx1YjQ1MCBcdWM4MWNcdWFjZjFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD41PTI8c3VwPjI8XC9zdXA+KzE8c3VwPjE8XC9zdXA+IDEzPTM8c3VwPjI8XC9zdXA+KzI8c3VwPjI8XC9zdXA+IDE3PTQ8c3VwPjI8XC9zdXA+KzE8c3VwPjI8XC9zdXA+IDQxPTU8c3VwPjI8XC9zdXA+KzQ8c3VwPjI8XC9zdXA+PFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYywgMTEsIDE5LCAyMywgMzFcdWM3NDAgXHVjODFjXHVhY2YxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhZDZjXHVhYzA0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMjE4XHViOTdjIFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBMXHVhY2ZjIFVcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChMICZsZTsgVSAmbHQ7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgTFx1YWNmYyBVXHVhYzAwIC0xXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNTVjIFx1YzkwNFx1YzVkMCBMIFUgeCB5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIExcdWFjZmMgVVx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWMxMlx1Yzc3NFx1YWNlMCwgeFx1YjI5NCBcdWFkNmNcdWFjMDQgW0wsVV1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMTgsIHlcdWIyOTQgW0wsVV1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjJm5ic3A7XHVjMThjXHVjMjE4XHVjOTExIFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTEzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmVybWF0XHUyMDE5cyBDaGlyc3RtYXMgVGhlb3JlbSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYSBsZXR0ZXIgZGF0ZWQgRGVjZW1iZXIgMjUsIDE2NDA7IHRoZSBncmVhdCBtYXRoZW1hdGljaWFuIFBpZXJyZSBkZSBGZXJtYXQgd3JvdGUgdG8gTWFyaW4gTWVyc2VubmUgdGhhdCBoZSBqdXN0IHByb3ZlZCB0aGF0IGFuIG9kZCBwcmltZSBwIGlzIGV4cHJlc3NpYmxlIGFzIHAgPSBhPHN1cD4yPFwvc3VwPiArIGI8c3VwPjI8XC9zdXA+IGlmIGFuZCBvbmx5IGlmIHAgaXMgZXhwcmVzc2libGUgYXMgcCA9IDRjKzEuIEFzIHVzdWFsLCBGZXJtYXQgZGlkblx1MDA5MHQgaW5jbHVkZSB0aGUgcHJvb2YsIGFuZCBhcyBmYXIgYXMgd2Uga25vdywgbmV2ZXIgd3JvdGUgaXQgZG93bi4gSXQgd2Fzblx1MDA5MHQgdW50aWwgMTAwIHllYXJzIGxhdGVyIHRoYXQgbm8gb25lIG90aGVyIHRoYW4gRXVsZXIgcHJvdmVkIHRoaXMgdGhlb3JlbS4gVG8gaWxsdXN0cmF0ZSwgZWFjaCBvZiB0aGUgZm9sbG93aW5nIHByaW1lcyBjYW4gYmUgZXhwcmVzc2VkIGFzIHRoZSBzdW0gb2YgdHdvIHNxdWFyZXM6PFwvcD5cclxuXHJcbjxwPjU9MjxzdXA+MjxcL3N1cD4rMTxzdXA+MTxcL3N1cD4mbmJzcDsxMz0zPHN1cD4yPFwvc3VwPisyPHN1cD4yPFwvc3VwPiZuYnNwOzE3PTQ8c3VwPjI8XC9zdXA+KzE8c3VwPjI8XC9zdXA+Jm5ic3A7NDE9NTxzdXA+MjxcL3N1cD4rNDxzdXA+MjxcL3N1cD48XC9wPlxyXG5cclxuPHA+V2hlcmVhcyB0aGUgcHJpbWVzIDExLCAxOSwgMjMsIGFuZCAzMSBjYW5ub3QgYmUgZXhwcmVzc2VkIGFzIGEgc3VtIG9mIHR3byBzcXVhcmVzLiBXcml0ZSBhIHByb2dyYW0gdG8gY291bnQgdGhlIG51bWJlciBvZiBwcmltZXMgdGhhdCBjYW4gYmUgZXhwcmVzc2VkIGFzIHN1bSBvZiBzcXVhcmVzIHdpdGhpbiBhIGdpdmVuIGludGVydmFsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpZmllZCBvbiBhIHNlcGFyYXRlIGlucHV0IGxpbmUgdGhhdCBzcGVjaWZpZXMgdHdvIGludGVnZXJzIEwsIFUgd2hlcmUgTCAmbGU7IFUgJmx0OyAxLDAwMCwwMDA8XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBpbmNsdWRlcyBhIGR1bW15IHRlc3QgY2FzZSB3aXRoIGJvdGggTCA9IFUgPSAmbWludXM7MS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIHRoZSByZXN1bHQgdXNpbmcgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbkxcdTAwMDIgVSBcdTAwMDJ4XHUwMDAyIHk8XC9wcmU+XHJcblxyXG48cD53aGVyZSBMIGFuZCBVIGFyZSBhcyBzcGVjaVx1MDA5M2VkIGluIHRoZSBpbnB1dC4geCBpcyB0aGUgdG90YWwgbnVtYmVyIG9mIHByaW1lcyB3aXRoaW4gdGhlIGludGVydmFsIFtMLCBVXSAoaW5jbHVzaXZlLCkgYW5kIHkgaXMgdGhlIHRvdGFsIG51bWJlciBvZiBwcmltZXMgKGFsc28gd2l0aGluIFtMLCBVXSkgdGhhdCBjYW4gYmUgZXhwcmVzc2VkIGFzIGEgc3VtIG9mIHNxdWFyZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d