Message Decoding

You are given one or more encoded messages. Each message is a string containing only digits between 0 and 9. The encoding follows the mapping where 'A' = 1, 'B' = 2, ..., 'Z' = 26.

Your task is to determine the total number of ways to decode each message. If a message cannot be decoded, the number of ways is 0.

For example, the message "12" can be decoded as "AB" (1 2) or "L" (12), so the result is 2.

Note: Any leading zero makes the message invalid when standing alone.

inputFormat

The first line of input contains an integer T representing the number of messages. Each of the following T lines contains a single non-empty string representing an encoded message.

outputFormat

Output T lines, each line containing the total number of ways to decode the corresponding message.

## sample

2
12
226

2
3

</p>