#P1727. 光棍的yy

光棍的yy

yy经常遇见一个奇怪的事情,每当他看时间的时候总会看见11:11,这个很纠结啊

现在给你m个1,你可以把2个1组合成一个2,这样就不是光棍了,问这样的组合有多少种??

例如(111  可以拆分为 111 12 21  有三种)

Input

第一行输入一个n表示有n个测试数据
以下n行,每行输入m个1
(1 <= n,m <= 200)

Output

输出这种组合种数,占一行

Sample Input

3
11
111
11111

Sample Output

2
3
8

HINT

Source