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
2023-12-03 18:19:26 Simes
I know there are a lot of ACs, but is the input really valid? After checking for -1, and trimming off any spaces, I get an assertion failure when checking each character in the input is a digit. I've tried ignoring all non-digit characters, and even splitting the input on any non-digit, but still get WA. What is the secret to AC here? My code passes all test cases on uDebug.
2020-11-03 18:23:57 David
Open problem to Java!

Last edit: 2020-11-03 18:24:08
2020-04-22 16:00:58
for doing large calculation we use super computer or other advaced computer but we sometime need to access number which can't fit in our computer but we can do it by taking it string..nice
2019-10-25 19:24:43
for 0 ans is 0 should be cleared.....................
2019-02-05 19:32:02
observe that it's not 2^31 rather 10^31 so this value won't fit in long long

Last edit: 2019-02-05 19:32:11
2017-09-06 13:49:09
Implemented within 2 mins, then noticed that Java wasn't allowed.... Lol
2017-04-14 03:52:53 candide
Elementary but tedious to get right, C is not Python! Tests are weak, for instance a file returning incorrectly 1000 (instead of 1002) to 9010 as input got accepted. The correct answer for 0 as input remains unclear (the valid answer is 0, not 1).

Last edit: 2017-04-14 16:57:28
2016-12-29 11:46:38
doing without big integer....really a workout!
2016-11-06 13:07:57 sonu
if you are getting wa then do check for 92
2016-03-09 15:00:41 topke
Clarify 0 test case, cause right answer by problem statement is 1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.