1002. 今晚吃……

题目描述

今天的比赛结束了！疲惫的 Hare 翻了翻她发布的帖子。“去尝尝这几个月才开门的 $s$ 餐厅吧！”看到某参赛选手发布的评论，Hare 决定去探一探这家 $s$ 餐厅。她打开地图搜索，却惊奇地发现没有任何一家餐厅的名字和其相匹配。

现在，为了寻找匹配的餐厅，Hare 需要选取 01 字符串 $s$ 的一个子序列并将其拼成字符串 $s_{\text{sub}}$，使得 $s_{\text{sub}}$ 表达的信息与 $s$ 一致。你需要帮助 Hare 计算这个子序列长度的最小可能值。

在本题中，一个 01 字符串 $t$ 的信息是指全集 $U=\{$00，01，10，11$\}$ 的子集 $E_t$，使得所有 $E_t$ 中的元素都是 $t$ 的子串，所有 $U\setminus E_t$ 中的元素都不是 $t$ 的子串。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 7\times10^4$）表示测试数据组数。

接下来对于每一组测试数据：

输入的唯一一行包含一个 01 字符串 $s$（$2\le|s|$）。

保证所有测试数据输入的 01 字符串长度之和不超过 $3\times10^6$。

输出格式

对于每一组测试数据，输出包含一行一个整数表示子序列长度的最小可能值。

样例输入

2
1010100
00011101011010

样例输出

4
5

提示


对于第一组测试数据，由上图可知，$s_{\mathrm{sub}}=$ 1001 是满足条件的子序列。可以证明该情况的长度最小。

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1002