Decode Messages

You are given a series of messages, each consisting of a string of digits. Each digit or pair of digits may represent a letter using the mapping \(1 \to a,\ 2 \to b,\ \ldots,\ 26 \to z\). The message is decoded by interpreting the digits as either single digits or as valid two-digit numbers (from 10 to 26).

Note that a valid two-digit decoding cannot overlap with another digit. For example, the string "123" can be decoded in 3 ways: "a b c" (1, 2, 3), "a w" (1, 23) and "l c" (12, 3). Your task is to calculate the total number of ways each message can be decoded.

It is guaranteed that all input messages will contain only digit characters. Beware of cases where the message starts with '0' which are invalid.

inputFormat

The input is read from stdin and consists of:

1. An integer \(T\) representing the number of messages.
2. \(T\) lines, each containing a string composed of digits that represent a message.

For example:

3
123
226
06

outputFormat

For each message, output a single integer on a new line representing the total number of ways the corresponding message can be decoded. The output is written to stdout.

For the example above, the expected output would be:

3
3
0

## sample

1
123

3