Decode Ways

Given a non-empty string of digits, determine the total number of ways to decode it into letters using the mapping: (1 \to A, 2 \to B, \ldots, 26 \to Z). A decoding is valid if every digit or valid two-digit number (between 10 and 26 inclusive) is mapped to a corresponding letter. For example, the string "12" can be decoded as "AB" (1,2) or "L" (12). This problem requires you to implement an efficient solution (using dynamic programming) where the recurrence relation is given by (dp[i] = dp[i-1] + dp[i-2]) when valid, with appropriate checks for the special case of '0'.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (t) representing the number of test cases. Each of the following (t) lines contains a non-empty string of digits to be decoded.

outputFormat

For each test case, output a single integer on a new line representing the total number of ways to decode the given string. Output is written to standard output (stdout).## sample

4
12
226
0
2101

2
3
0
1