Программа: рекурсивная функция с делением нацело для многих n
Условие
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n < 4;
F(n) = F(n // 2) + F(n − 3), если n ≥ 4 и n чётно;
F(n) = F(n − 1) − F(n // 3) + n, если n ≥ 4 и n нечётно.
Здесь // — деление нацело (целая часть частного).
Напишите программу, которая вычисляет значения функции F для нескольких заданных n.
Входные данные: в первой строке — число T (1 ≤ T ≤ 10), во второй — T натуральных чисел n1, …, nT через пробел (1 ≤ ni ≤ 200 000).
Выходные данные: T строк — значения F(n1), …, F(nT) в порядке ввода.
Пример.
Входные данные:
3
5 10 20Выходные данные:
7
18
70