给定字符串研究所（RIGS）正在研究一种构建无限字符串的新方法。

最初有一个空字符串 $S_0^{(k)} = \varepsilon$。此后，该字符串的每个新版本都按以下方式创建：

将当前版本的字符串重复 $k$ 次，并在每两个相邻的重复项之间插入一个任意字符。在构建所有版本的过程中，使用的数字 $k$ 必须相同，但插入的字符可以不同。这种构建方式最终会产生一个无限长度的字符串 $S_{\infty}^{(k)}$。

为了便于说明，我们考虑一系列字符串（当 $k = 3$ 时）：

$$S_0^{(3)} = \varepsilon \text{（空字符串）}$$ $$S_1^{(3)} = \text{rt} \quad (S_1^{(3)} = \varepsilon \text{ r } \varepsilon \text{ t } \varepsilon)$$ $$S_2^{(3)} = \text{rt x rt r rt}$$ $$S_3^{(3)} = \text{rtxrtrrt a rtxrtrrt r rtxrtrrt}$$ $$\dots$$ $$S_{\infty}^{(3)} = \text{rtxrtrrtartxrtrrtrrtxrtrrtzrtxrtrrtartxrt}\dots$$

给定一个长度为 $n$ 的字符串 $A$，它是 $S_{\infty}^{(k)}$ 的前缀，求使得该条件成立的最小的 $k$。

换句话说，你的任务是找到最小的 $k$，使得可以通过上述方式构建一个字符串 $S_{\infty}^{(k)}$，并让 $A$ 作为它的前缀。

输入格式

每个输入文件包含多个测试用例。输入的第一行包含一个整数 $T$ — 测试用例的数量。接下来的 $T$ 行中，每行描述一个测试用例。测试用例非空，且仅包含小写英文（拉丁）字母。

测试用例的数量不超过 $10^5$。文件中所有测试用例的长度之和不超过 $10^6$。

输出格式

输出文件必须恰好包含 $T$ 行。每行必须包含对应测试用例的最小 $k$ 值。

样例

输入样例 1

2
abacabab
rtxrtrrtartxrtrrtrrtxrt

输出样例 1

2
3