دنباله ${f_n}$ به این صورت ساخته می‌شود:

اگر $n = 1$ باشد: $f_{n} = 1$ اگر $n > 1$ باشد: $f_{n} = gcd(f_{n - 1}, n) + n^2$

منظور از $gcd(a, b)$ یعنی بزرگ‌ترین مقسوم‌علیه مشترک $a$ و $b$ است.

از شما می‌خواهیم به ازای $t$ مقدار مختلف برای $n$ مقدار $f_{n}$ را پیدا کنید.

ورودی

در سطر اول ورودی عدد صحیح و مثبت $t$ آمده است.

$1 \le t \le 1,000,000$

در $t$ سطر بعدی، در هر سطر یک عدد صحیح و مثبت $n$ داده می‌شود.

$1 \le n \le 1000 \ 000 \ 000$

خروجی

خروجی شامل $t$ سطر است که در سطر $n$ ام آن مقدار $f$ به ازای عدد $i$ ام داده شده در ورودی را چاپ کنید.

$f(1) = 1$
$f(2) = gcd(f(1), 2) + 2^2 = gcd(1, 2) + 4 = 1 + 4 = 5$
$f(3) = gcd(f(2), 3) + 3^2 = gcd(5, 3) + 9 = 1 + 9 = 10$
$f(4) = gcd(f(3), 4) + 4^2 = gcd(10, 4) + 16 = 2 + 16 = 18$
$f(5) = gcd(f(4), 5) + 5^2 = gcd(18, 5) + 25 = 1 + 25 = 26$

ارسال پاسخ برای این سؤال