Photo by petr katrochvil cc0 1.0

你最近被乡村与城市道路通信公司（Rural and Municipal Roadway Communications）雇佣，负责管理主要高速公路上一块滚动显示屏上的信息。

令你惊讶的是，这些显示屏非常原始。每次需要更改信息时，你都必须手动输入（没有内存可以预先加载信息列表）。

奇怪的是，发布信息的唯一方法是使用内置的栈（stack）。你可以将一个字符压入（push）栈顶，可以弹出（pop）栈顶的字符，也可以打印（print）栈顶的字符。

出于无聊，或者也许是人类普遍希望用尽可能少的工作量来完成任务的本能，你想知道：要打印老板要求你显示的某条信息，最少需要多少次 push、pop 和 print 操作？哦，你还必须确保在结束时栈是空的，以便下次老板要求你输入新信息时做好准备。

例如，如果我们想打印信息 abba 然后清空栈，可以执行以下操作。请注意，下方记录的栈内容中，栈顶在右侧。

事实上，这是打印出完全相同的 abba 信息并使栈变空所需的最少操作次数。

输入格式

输入的第一行是一个正整数 $T \le 30$，表示测试用例的数量。

接下来的 $T$ 行，每行包含一个由任意可打印字符组成的字符串。每行的第一个和最后一个字符都是非空白字符。每行至少有 $1$ 个字符，最多有 $200$ 个字符。

输出格式

对于输入中的每个字符串，在一行中输出在显示屏上打印该字符串并使栈变空所需的最少操作次数。

样例

输入样例 1

4
d
abba
rollover ahead
ogopogo spotted!

输出样例 1

3
8
34
38