Candy Rotation

Time limit2sMemory limit128 MB

Summary

Given N cells in a circle, simulate digit-sum-based clockwise moves from every starting cell and find the maximum count of distinct cells visited before a repeat.

Level: Medium4 of 10
Topics: Simulation, Brute force, Math
Solved: No attempts yet

Problem

Sejun has a circular candy container with N cells. The cells are arranged in a circle and numbered from 1 to N clockwise.

First, Sejun may place the candy in any one cell. After that, look at the number of the cell containing the candy, compute the sum of its decimal digits, and move the candy clockwise by that many cells. If the candy is in cell 123, it moves 1 + 2 + 3 = 6 cells clockwise. Repeat this movement until the candy reaches a cell that has already been visited. The initial cell is also counted as visited.

Given N, determine the maximum number of distinct cells that can be visited by choosing the initial cell optimally.

Input

The first line contains a natural number N. N is at most 200,000.

Output

Print the maximum number of distinct cells that can be visited.

Examples4

Example 1
Input
```
4
```
Expected output
```
3
```
Example 2
Input
```
5
```
Expected output
```
4
```
Example 3
Input
```
17
```
Expected output
```
11
```
Example 4
Input
```
566
```
Expected output
```
176
```