背景

17收到了一份密文：一个只包含字母的消息被加密之后变成了一个只包含数字的字符串。
幸好17知道加密的规则：A加密为1，B加密为2，…，Z加密为26。
现在给定一个已经被加密的只包含数字的字符串，求该字符串有多少种被解密的方法。

输入

一个正整数n表示测试案例的数量。
从第二行到第n+1行，每行都是一个只包含数字的字符串。

输出

针对每组案例，输出该字符串有多少种被解密的方法。每行输出后都要换行。

样例输入

2
12
123

样例输出

2
3

提示

12可以解密为AB,也可以解密为L。