#546. Look and Say

Look and Say 序列是一种很有意思的序列，它的首项是 1，之后的每一项的数字都通过对前面一项的数字“边看边说”得到。

形式化地，设 $a_n$ 表示序列第 $n$ 项，且 $S(x,y)=\underbrace{yy\cdots y}_{x}$，是由数字 $y$ 重复 $x(x\ge 1)$ 次构成的字符串。若 $a_{n-1} = S(x_1,y_1)+S(x_2,y_2)+\cdots+S(x_k,y_k)$，且 $\forall i(1\le i<k), y_i\ne y_{i+1}$，其中 "$+$" 表示字符串连接，那么 $a_n = x_1y_1x_2y_2\cdots x_ky_k$。容易知道在上述约束下 $a_n$ 可以由 $a_{n-1}$ 唯一确定。

因为序列的第一项只有 1 个 1 ，所以第二项就是 11； 因为第二项有 2 个 1，所以第三项就是 21； 因为第三项有 1 个 2 和 1 个 1，所以第四项就是 1211。 以此类推。该数列的前几项为

现在给你一个由数字组成的字符串，确定这个字符串出现在 Look and Say 序列中的第几位。数据保证序列中一定会出现给出的字符串。

第一行一个正整数 $T(1\le T\le 50)$，表示测试数据的组数。

对于每一组测试数据，输入一行一个由数字组成的字符串 $s$，保证其对应的数在序列中出现过。

保证所有 $T$ 个测试数据中 $s$ 的总长度 $\sum|s| \le 5\times 10^6$。

对于每一组测试数据，输出一行一个非负整数，表示 $s$ 出现在序列中的第几位。

输入样例

1
312211

输出样例

6