SUBP - Subsequence Problem
Given a string S which contains only digit-characters. How many subsequences(P) can be obtained from S such that every digit is strictly greater than all previous digits in that subsequence.
As for example if S=7598 then there are 8 subsequences which follow the above constraint. These are 7,5,9,8,79,78,59,58. Notice that 7598 is not a required subsequence because 7>5 and 9>8.
Note: A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains a string S. The length of S does not exceed 100. S does not contain any leading zeros.
Output
For each case, print the case number and P.
Sample Input |
Output for Sample Input |
2 4 7598 |
Case 1: 1 |
Problem Setter: Md Abdul Alim, CEO and Founder at CodeMask
Added by: | Md Abdul Alim |
Date: | 2014-06-16 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Own Problem |