• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

دنباله \(\{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\)