Простые числа нового вида
(Время: 0,5 сек. Память: 32 Мб Сложность: 88%)
Определите количество простых чисел, не превосходящих N, которые представимы в виде x2 + y4, где x, y – натуральные числа.
Входные данные
В первой строке входного файла INPUT.TXT находится натуральное число Q – количество запросов (1 ≤ Q ≤ 1000).
В следующей строке через пробел находятся Q натуральных чисел N (1 ≤ N ≤ 2×1010).
Выходные данные
В выходной файл OUTPUT.TXT выведите на каждый запрос ответ на задачу через пробел.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
20 | 3 |
| 2 | 2
100 1 | 6 0 |
Пояснение
В первом примере существуют только три числа, удовлетворяющие условию задачи, не превосходящие 20: 2 = 12 + 14, 5 = 22 + 14 и
17 = 12 + 24.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
