Taco Decoding Challenge

You are given a non-empty string s consisting of digits. Your task is to determine the total number of ways to decode it into letters, where 'A' is represented by 1, 'B' by 2, ..., and 'Z' by 26.

The decoding follows these rules:

• A single digit (from 1 to 9) can be decoded as a letter.
• A pair of digits between 10 and 26 (inclusive) can be decoded as a letter.
• The digit '0' does not correspond to any letter on its own.

The underlying recurrence relation for this decoding is given by the formula

\( dp[i] = \begin{cases} dp[i-1] & \text{if } 1 \leq s[i-1] \leq 9, \\ dp[i-2] & \text{if } 10 \leq (s[i-2]s[i-1]) \leq 26. \end{cases} \)

Note: In cases where the string starts with '0' or contains invalid sequences, the number of decodings is 0.

inputFormat

The input is read from stdin and is structured as follows:

1. The first line contains an integer t (the number of test cases).
2. The following t lines each contain a single string s consisting of digits.

outputFormat

For each test case, output the number of possible decoded messages on a separate line. The answers should be written to stdout.

## sample

3
123
27
10

3
1
1

</p>