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)


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

hide comments
2015-12-29 18:42:54
good questin, implemented my bigint
2015-07-26 12:06:31 Satyam Mishra
Nice and easy one...
ACed in 1 go. :)
2015-07-22 15:07:16 :.Mohib.:
Very good question.... :)
You need to write your own container...!! ;)

Last edit: 2015-07-22 17:37:12
2015-07-13 09:37:23
test cases with answers:
0 0
1 1
10 2
82 10
892 100
8991 99
8992 1000
2015-02-12 20:12:17 :D
Result for 0 is 0, as in you don't have to use any digits.
2014-11-05 14:42:46 Stupider
"Note: There are no extra new lines between different numbers."

I got error using gets to read line by line and AC with scanf("%s"), jesus -.-
2014-10-24 22:57:42 Archit Jain
easy
2014-06-27 21:09:48 Ouditchya Sinha
Finally AC! :)
Note: There are no extra new lines between different numbers.

Last edit: 2014-02-19 12:33:42
2014-06-27 21:09:48 anurag garg
biginteger rocks
2014-06-27 21:09:48 Bhavik
it seems easy but giving wa!!...any tricky cases still... though i have tested for all boundary cases


EDIT: Got AC though i only changed int array to char array for the ans..but still i don't know why my previous solutions were not accepted!!

Last edit: 2014-02-18 14:13:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.