Decode Ways

Given a non-empty string s containing only digits, determine the total number of ways to decode it based on the mapping where \(1 \to A, 2 \to B, \dots, 26 \to Z\). For instance, the string "12" can be decoded as either "AB" (\(1\,2\)) or "L" (\(12\)).

If the string starts with a zero or contains an invalid encoding, the output is 0. The input consists of multiple test cases, and you are required to compute the number of decoding ways for each case.

inputFormat

The first line of input contains an integer T indicating the number of test cases. Each of the next T lines contains a string of digits representing a test case.

outputFormat

For each test case, print the number of valid decoding ways on a new line.

3
12
226
0

2
3
0