简单序列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Naix_x有一天发现一个有趣的序列如下:

    a1 = 15;

    a2 = 195;

    a3 = 1995;

    a4 = 19995;

    ......

    an = 19...5;(中间n-19)

    你能帮他计算前n项和Sn的后四位的和吗?

Input

 输入数据有多组(保证不多于300组),每行有一个整数n(1<=n<=1000000).

Output

 每组输出只有一个整数,前n项和Sn的后四位的和。

Sample Input

1
3
5

Sample Output

6
9
17

Hint

 

Source