Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Ternary String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string $$$s$$$ such that each its character is either 1, 2, or 3. You have to choose the shortest contiguous substring of $$$s$$$ such that it contains each of these three characters at least once.

A contiguous substring of string $$$s$$$ is a string that can be obtained from $$$s$$$ by removing some (possibly zero) characters from the beginning of $$$s$$$ and some (possibly zero) characters from the end of $$$s$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 20000$$$) — the number of test cases.

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 200000$$$). It is guaranteed that each character of $$$s$$$ is either 1, 2, or 3.

The sum of lengths of all strings in all test cases does not exceed $$$200000$$$.

Output

For each test case, print one integer — the length of the shortest contiguous substring of $$$s$$$ containing all three types of characters at least once. If there is no such substring, print $$$0$$$ instead.

Example

Input

7 123 12222133333332 112233 332211 12121212 333333 31121

Output

3 3 4 4 0 0 4

Note

Consider the example test:

In the first test case, the substring 123 can be used.

In the second test case, the substring 213 can be used.

In the third test case, the substring 1223 can be used.

In the fourth test case, the substring 3221 can be used.

In the fifth test case, there is no character 3 in $$$s$$$.

In the sixth test case, there is no character 1 in $$$s$$$.

In the seventh test case, the substring 3112 can be used.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 04:23:13 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|