MINNUM - Minimum Number


Prana has given a number. Now she wonder what will be the maximum number of digits that the sum of these digits is equal to the given number. After thinking sometimes she laughed at herself, cause the number is infinite.

Now your task is to find the minimum number of digits that the sum of these digits is equal to the given number.

Input

The input contain a single integer N (0 ≤ N ≤ 1031). The input is terminated by a line containing -1.

Output

Output a single line the number of digits that the sum of the digits is equals to the given number. See the sample input/output for exact formatting.

Sample

Input
11
1
-1

Output
2
1

Explanation

For the first test case given number is 11. Some possible way to make 11 is

7+4=11 which costs 2 digits.

2+3+6=11 which costs 3 digits.

1+2+3+5=11 which costs 4 digits.

1+2+3+0+5=11 which costs 5 digits.

So, here first example costs the minimum number of digits which is 2.

Note: There are no extra new lines between different numbers.

Problem setter: Abu Sufian, Dept. of CSE, Bangladesh University of Business and Technology (BUBT)


hide comments
Luka: 2014-06-27 21:09:48

for 892, answer is 100
Caused me WAs due to this

nitesh kumar: 2014-06-27 21:09:48

take care of different corner cases!!

akulsareen: 2014-06-27 21:09:48

Easy enough. Careless error cost me WAs.

Abhinav Gupta: 2014-06-27 21:09:48

I am getting wrong answer..Is there any tricky case or it is a problem of input size..As java is not given in the languages constraint..

shiv prasad chabarval: 2014-06-27 21:09:48

easy one
don't know why accuracy iz below 15% :D

vank: 2014-06-27 21:09:48

getting wrong answer... give more test cases..

Last edit: 2013-12-24 11:17:39
Aditya Gourav: 2014-06-27 21:09:48

could yu see my solution, its giving wrong answer time and again..
10704218

[Lakshman]: 2014-06-27 21:09:48

providing answer for below case will spoil the problem

Andrey Maksimenko: 2014-06-27 21:09:48

Is it something wrong with input description?

Shipu : NO

Last edit: 2013-11-20 19:45:17

Added by:Shipu Ahamed
Date:2013-09-18
Time limit:1s
Source limit:3100B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP PAS-GPC PAS-FPC