Лонги Problemi

Longi riyaziyyatdan yaxşı baş çıxarır və bəzi gözəl alqoritmlərlə həll edilə bilən çətin riyazi məsələlər üzərində düşünməyi sevir. Belə bir məsələ ortaya çıxdı:

Verilmiş tam ədəd $n$ üçün, bütün $1\le i\le n$ üçün $\sum gcd(i,n)$ hesablayın.

"Ah, mən bilirəm, mən bilirəm!" — Longi qışqırdı! Bəs siz bilirsinizmi? Xahiş edirik, bu məsələni həll edin.

Giriş verilənləri

Hər bir sətir bir ədəd $n(1<n<2^{31})$ ehtiva edir.

Çıxış verilənləri

Hər bir $n$ dəyəri üçün, hər bir sətirdə bütün $1\le i\le n$ üçün $\sum gcd(i,n)$ cəmini çıxarın.

Nümunələr