Fibonaccin lukujono (F_n) on erittäin tunnettu lukujono, ja se määritellään seuraavasti:

• F_0 = 0
• F_1 = 1
• F_n = F_{n - 1} + F_{n - 2}, jos n \geq 2.

Paljon vähemmälle huomiolle on jäänyt Uolevinaccin lukujono (U_n), joka määritellään seuraavasti:

• U_0 = 0
• U_1 = 1
• U_n = U_{\lfloor n/2\rfloor} + U_{\lfloor n/3\rfloor} + U_{\lfloor n/4\rfloor} + U_{\lfloor n/5\rfloor} + \ldots + U_{\lfloor n/n\rfloor}, jos n \geq 2.

Merkintä \lfloor x \rfloor tarkoittaa lukua x pyöristettynä alaspäin kokonaisluvuksi.

Syöte

Syötteenä annetaan yksi kokonaisluku n.

Tuloste

Tulosteen tulee olla luku U_n.

Rajat

• 1 \leq n \leq 10^5
• Voit olettaa, että U_n on enintään 10^9.

Esimerkki

Syöte:

10

Tuloste:

13

Selitys:

• U_1 = 1
• U_2 = U_1 = 1
• U_3 = U_1 + U_1 = 2
• U_5 = U_2 + U_1 + U_1 + U_1 = 4
• U_{10} = U_5 + U_3 + U_2 + U_2 + U_1 + U_1 + U_1 + U_1 + U_1 = 13