We call an integer Sticks if its decimal representation contains only digit 1.

Let S(n) be the sticks with n digits, find the sum of digits of S(n)²

For example, S(9)²=12345678987654321, its sum of digits is 81.

Input

Each line contains an integer represents n(1 ≤ n ≤ 10¹⁸).

Input is terminated by EOF, and contains at most 100 lines.

Output

For each n, print an integer represents the answer.

Example

Input:
9
10

Output:
81
82