e-olymp
Yarışlar

Euler Function

Longge`s problem

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes:

Given an integer n (1 < n < 231), you are to calculate ∑gcd(i, n) 1in.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

Input

Each line contains one number n.

Output

For each number n print ∑gcd(i, n) 1in in a separate line.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
2
6
Çıxış verilənləri #1
3
15