Fermat's Christmas Theorem#1629
In a letter dated December 25, 1640, the great mathematician Pierre de Fermat wrote to Marin Mersenne that he had just proved that an odd prime can be expressed as p = a^2 + b^2 if and only if can be expressed as p = 4c + 1. As usual, Fermat did not include the proof in the letter, and as far as we know, never wrote it down anywhere. It turned out that even 100 years later, no one other than Euler proved this theorem. For example, each of the following primes can be expressed as the sum of two squares:
5 = 2^2 + 1^2, 13 = 3^2 + 2^2, 17 = 4^2 + 1^2, 41 = 5^2 + 4^2
On the other hand, the primes , , , and cannot be expressed as the sum of two squares. Write a program to count the number of primes that can be expressed as a sum of two squares within a given interval.
Your program will be tested on one or more test cases. Each test case is given on a separate line of the input and specifies two integers where L \leq U < 1000000.
The last line of the input file contains a dummy test case with L = U = -1.
For each test case, output the result in the following format:
L U x y
where and are as specified in the input. is the total number of primes within the interval (inclusive), and is the total number of primes (also within ) that can be expressed as the sum of two squares.
Example 1