## ANARC05H - Chop Ahoy! Revisited!

Given a non-empty string composed of digits only, we may group these digits into sub-groups (but maintaining their original order) if, for every sub-group but the last one, the sum of the digits in a sub-group is less than or equal to the sum of the digits in the sub-group immediately on its right. Needless to say, each digit will be in exactly one sub-group.

For example, the string 635 can only be grouped in one sub-group [635] or in two sub-groups as follows: [6-35] (since 6 < 8.) Another example is the string 1117 which can be grouped in one sub-group [1117] or as in the following: [1-117], [1-1-17], [1-11-7], [1-1-1-7], [11-17] and [111-7] but not any more, hence the total number of possibilities is 7.

Write a program that computes the total number of possibilities of such groupings for a given string of digits.

### Input

Your program will be tested on a number of test cases. Each test case is speciﬁed on a separate line. Each line contains a single string no longer than 25, and is made of decimal digits only.

The end of the test cases is identiﬁed by a line made of the word "bye" (without the quotes.) Such line is not part of the test cases.

### Output

For each test case, write the result using the following format:

`k. n`

where k is the test case number (starting at 1,) and n is the result of this test case.

### Example

```Input:
635
1117
9876
bye

Output:
1. 2
2. 7
3. 2```

hide comments
 avinash kumar: 2012-12-15 19:29:47 i am trying to solve it by recursion with for loop. can i get some bigger test case rohitjv: 2012-12-11 04:35:07 very easy dp :) AC in first attempt Last edit: 2012-12-11 04:35:44 gourav: 2012-09-29 07:52:03 yipeeeeeeee!! 15th problem now ;) cool Surya: 2012-06-27 05:33:00 @ ;) : Max string length is only 25. So its not a matter of time. Even recursion will do without deeping out! npsabari: 2012-06-26 20:15:18 Naive Brute Force method is getting AC in 0.00 sec!! data: 2012-06-19 18:35:34 easy one:) Romal Thoppilan: 2012-06-11 07:13:46 yaah .. just changing gets() to scanf("%s") worked !! M LOHIT: 2012-05-23 13:24:34 In test cases lines are ending with "\r\n" (Windows style) instead of '\n'. Don't use gets() to read input. Use scanf(). Kashyap Krishnakumar: 2011-05-05 01:31:37 Nice problem. Some submissions in "TEXT" have been accepted. I guess it has to be disabled. Last edit: 2011-05-05 01:33:26 Jacob: 2010-01-20 19:05:00 Dodgy white space on the input here too.

 Added by: ~!(*(@*!@^& Date: 2009-07-05 Time limit: 1s-2s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: ANARC 2005