wjj 最近打算玩 Persona 5，可是出身贫民窟的他没钱买游戏和主机。这个时候土豪 zzh 给了他一道题，并说，要是 wjj 可以做出这道题，就送给他游戏和主机。这个问题是：
给定一个 $01$ 串 $s$，请你找到一个最短的非空串 $t$，使得 $t$ 不是 $s$ 的子串。
zzh 称这个问题为 P5，现在 wjj 向你寻求帮助，让你帮他过掉 P5。
子串：串中连续的一段区间，称为子串。
非空串：串长至少为 $1$ 的串。
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
仅一行，一个字符串 $s$，含义见题目描述。
保证 $1 \leq T \leq 30,$ $1 \leq |s| \leq 4.5 \times 10^6$ 。其中 $|s|$ 表示 $s$ 的长度。
输入文件总大小不超过 30MB。
对于每组数据，输出一行，包含一个整数，表示最短的不是输入串子串的非空串的长度。
2
01
011002
3对于第一组数据，最短的符合条件的一个串为 $00$。
对于第二组数据，最短的符合条件的一个串为 $000$。