+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دنباله $\{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$