seuOJ546 - Look and Say

题目描述

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

形式化地，设 ana_n 表示序列第 nn 项，且 S(x,y)=yy⋯y⏟xS(x,y)=\underbrace{yy\cdots y}_{x}，是由数字 yy 重复 x(x≥1)x(x\ge 1) 次构成的字符串。若 an−1=S(x1,y1)+S(x2,y2)+⋯+S(xk,yk)a_{n-1} = S(x_1,y_1)+S(x_2,y_2)+\cdots+S(x_k,y_k)，且 ∀i(1≤i<k),yi≠yi+1\forall i(1\le i<k), y_i\ne y_{i+1}，其中 "++" 表示字符串连接，那么 an=x1y1x2y2⋯xkyka_n = x_1y_1x_2y_2\cdots x_ky_k。容易知道在上述约束下 ana_n 可以由 an−1a_{n-1} 唯一确定。

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

1,11,21,1211,111221,312211,⋯1,11,21,1211,111221,312211,\cdots

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

输入格式

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

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

保证所有 TT 个测试数据中 ss 的总长度 ∑∣s∣≤5×106\sum|s| \le 5\times 10^6。

输出格式

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

样例

输入样例

1
312211

输出样例

6