该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

现在有一个仅包含1，2，3的字符串，徐老师准备取一个长度为3的子串，他希望有三种数字，如果无法做到，则他可以交换任意两个数字的位置，徐老师想知道至少需要操作多少次才能满足，如果不可能满足，则输出-1

Format

Input

第一行一个整数$T(\leq 10^2)$，表示测试组数

接下来T行，每行一个字符串$s(|s| \leq 10^5)$，表示输入的字符串，保证仅包含1，2，3

Output

输出一个整数，表示最小操作次数

Samples

2
123
111

0
-1

Limitation

1s, 1024KiB for each test case.