NIO is playing a new game. In this game, NIO has a sword with attack power represented by an integer AAA. Initially, A=0A=0A=0. There are also nnn enemies in the game. NIO has to kill them in order, which means NIO must kill the (i−1)(i-1)(i−1)-th enemy before killing the iii-th enemy for each iii (2≤i≤n2\le i\le n2≤i≤n). For the iii-th enemy, NIO can kill it if and only if A≡i(modn)A\equiv i \pmod{n}A≡i(modn).
Fortunately, NIO can upgrade his sword at any moment for any number of times. Each time NIO upgrades his sword, he first chooses an integer
xxx (
0≤x≤90\le x\le 90≤x≤9), then changes the attack power of the sword from
AAA to
10×A+x10\times A+x10×A+x.
NIO wants to minimize the number of times to upgrade the sword so that he can win the game as fast as possible. Can you help him to find the minimum times?