Народження теореми Ферма
У листі від 25 грудня 1640 р., великий математик П'єр де Ферма написав Марін Мерсенн, що він тільки що довів, що непарні прості числа р можна подати у вигляді р = a^2 + b^2, якщо і лише якщо р можна подати у вигляді p = 4c + 1. Як звичайно, Ферма не включив у лист доведення, і, наскільки нам відомо, ніде його і не записав. Так склалось, що і 100 років по тому, ніхто, крім Ейлера не довів цю теорему. Наприклад, кожне з наступних простих чисел можна подати у вигляді суми двох квадратів:
5 = 2^2 + 1^2 13 = 3^2 + 2^2 17 = 4^2 + 1^2 41 = 5^2 + 4^2
У той же час прості числа 11, 19, 23 і 31 не можуть бути виражені у вигляді суми двох квадратів. Напишіть програму для підрахунку кількості простих чисел, які можуть бути подані як сума квадратів у межах заданого інтервалу.
Вхідні дані
Ваша програма буде апробована на одному або декількох тестах. Кожен тестовий випадок вказано у окремому рядку вхідних даних, і визначає два цілих числа L, U де L ≤ U < 1000000.
Останній рядок вхідного файлу містить не опрацьовувані фіктивні значення L = U = −1.
Вихідні дані
Для кожного тесту виведіть результат, використовуючи наступний формат:
L U x y
де L і U задані у вхідних даних числа. x це загальна кількість простих чисел у інтервалі [L, U] (включно), а y загальна кількість простих чисел (також з інтервалу [L, U]), які можуть бути подані як сума квадратів.