Competitions

# 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** ≤ `2`

), you are to calculate ^{31}**∑gcd**(**i**,**n**) for all **1** ≤ **i** ≤ **n**.

"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 in a separate line **∑gcd**(**i**, **n**) for all **1** ≤ **i** ≤ **n**.

Input example #1

2 6 12

Output example #1

3 15 40