eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

YAPTCHA

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

У математического отдела появились проблемы. Из-за огромного количества автоматизированных программ, которые просматривали их страницы, они решили разместить на своих веб-страницах свои научные статьи. Чтобы получить к ним доступ, необходимо показать свои умения - а именно решить математическую загадку.

Тем не менее, тест оказался трудным для аспирантов и даже для некоторых профессоров. Поэтому математическому отделу следует написать программу, которая решает эту задачу.

Задача, которую предлагают любому посетителю стартовой страницы факультета математики, заключается в следующем: по заданному натуральному n вычислить

prb5730

где через [x] обозначено наибольшее целое, не большее x.

Входные данные

Первая строка содержит количество запросов t (t10^6). Каждый запрос состоит из одного натурального числа n (1n10^6).

Выходные данные

Для каждого n вывести в отдельной строке значение S[n].

Пример

Входные данные #1
13
1
2
3
4
5
6
7
8
9
10
100
1000
10000
Выходные данные #1
0
1
1
2
2
2
2
3
3
4
28
207
1609
Источник 2008 ACM CERC, Польша, Вроцлав, Ноябрь 28-30, Задача A