+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
دنباله $\{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$ام داده شده در ورودی را چاپ کنید.
# مثال
## ورودی نمونه ۱
```
5
1
2
3
4
5
```
## خروجی نمونه ۱
```
1
5
10
18
26
```
+ $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$