Fermat's Christmas Theorem

No attempts yetTime limit1sMemory limit128 MB

Problem

On December 25, 1640, the great mathematician Pierre de Fermat sent Marin Mersenne a letter containing the following claim.

I have just proved that an odd prime $p$ can be written as $p = a^2 + b^2$ if and only if $p$ can be written as $p = 4c + 1$.

The letter contained no proof; Euler proved it 100 years later. Indeed, $5,\ 13,\ 17,\ 41$ can each be written as a sum of two squares.

$$5 = 2^2 + 1^2 \qquad 13 = 3^2 + 2^2 \qquad 17 = 4^2 + 1^2 \qquad 41 = 5^2 + 4^2$$

By contrast, $11,\ 19,\ 23,\ 31$ cannot be written as a sum of two squares.

Here the two squares are squares of non-negative integers, and the prime $2 = 1^2 + 1^2$ also counts as a sum of two squares.

Given an interval $[L, U]$, write a program that counts how many primes in the interval can be written as a sum of two squares.

Input

The input consists of several test cases. Each test case is a single line containing two integers $L$ and $U$ separated by a space. ($-1{,}000{,}000 < L \le U < 1{,}000{,}000$)

In the last line, $L$ and $U$ are both equal to $-1$; this line is not processed.

Output

For each test case, print four integers $L$, $U$, $x$, $y$ on one line, separated by spaces. $L$ and $U$ are the given input values, $x$ is the number of primes in the interval $[L, U]$, and $y$ is the number of those primes that can be written as a sum of two squares.