Background

Special for beginners, ^_^

Description

记 $f(x)$ 为正整数 $x$ 的各位数字之和。

给出正整数 $n$ ，求 $min(f(k\times n))$ ，其中 $k$ 是正整数。

Format

Input

每个测试点数据不超过 $10^5$ 组。

每行一个正整数 $n(\le10^5)$ 。

Output

每行输出一个答案。

Samples

6
41

3
5

Limitation

1s, 1024KiB for each test case.