페르마의 크리스마스 정리

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가 공백으로 구분되어 주어진다. (-1,000,000 < L ≤ U < 1,000,000)

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

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