Decode Messages

Given an encoded message containing digits, determine the number of ways to decode it into a sequence of letters. In this encoding, 'A' is represented as 1, 'B' as 2, and so on up to 'Z' which is 26. A leading '0' is invalid and no valid decoding can start with it. Consider the recurrence relation:

\( dp[i] = \begin{cases} dp[i-1] & \text{if } s[i-1] \neq '0' \\ dp[i-2] & \text{if } 10 \leq s[i-2:i] \leq 26 \end{cases} \)

Your task is to compute the number of ways for each given encoded message.

inputFormat

The input is read from standard input (stdin) and contains multiple lines:

• The first line contains an integer T representing the number of messages.
• This is followed by T lines, each containing a non-empty string consisting of digits.

outputFormat

For each message, output on a separate line the number of ways it can be decoded. The output should be written to standard output (stdout).

## sample

1
12

2

</p>