You 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.

Difficulty: interview

Starter code:

Solutions:
t=int(input())
no_of_chars = 256
  
# Function to find smallest window  
# containing all characters of 'pat'  
def findSubString(string, pat):  
    len1 = len(string)  
    len2 = len(pat)  
    if len1 < len2:  
      
        return 0
    hash_pat = [0] * no_of_chars 
    hash_str = [0] * no_of_chars  
    for i in range(0, len2):  
        hash_pat[ord(pat[i])] += 1
  
    start, start_index, min_len = 0, -1, float('inf')  
    count = 0 # count of characters  
    for j in range(0, len1):  
        hash_str[ord(string[j])] += 1
        if (hash_pat[ord(string[j])] != 0 and
            hash_str[ord(string[j])] <= 
            hash_pat[ord(string[j])]):  
            count += 1
        if count == len2:  
            while (hash_str[ord(string[start])] >  
                   hash_pat[ord(string[start])] or
                   hash_pat[ord(string[start])] == 0):  
              
                if (hash_str[ord(string[start])] >  
                    hash_pat[ord(string[start])]):  
                    hash_str[ord(string[start])] -= 1
                start += 1
            len_window = j - start + 1
            if min_len > len_window:  
              
                min_len = len_window  
                start_index = start  
    if start_index == -1: 
        return 0
      
    # Return substring starting from  
    # start_index and length min_len  
    return min_len
while t:
    t-=1
    a=input()
    x="123"
    print(findSubString(a,x))
    


import sys
input = sys.stdin.readline

t = int(input())
out = []

for _ in range(t):
    s = input().strip()
    n = len(s)
    best = n + 1
    last1 = -best
    last2 = -best
    last3 = -best
    for i in range(n):
        c = s[i]
        if c == '1':
            last1 = i
        elif c == '2':
            last2 = i
        else:
            last3 = i
        curr = i - min(last1, last2, last3) + 1
        best = min(best, curr)
    if best <= n:
        out.append(best)
    else:
        out.append(0)
print(*out, sep = '\n')
    


from math import *
from random import *
for t in range(int(input())):
    s = input()
    n = len(s)
    p1 = -100000000000
    p2 = p1
    p3 = p1
    otv = 999999999
    for i in range(n):
        if s[i] == '1':
            otv = min(otv, i - min(p2, p3) + 1)
            p1 = i
        if s[i] == '2':
            otv = min(otv, i - min(p1, p3) + 1)
            p2 = i
        if s[i] == '3':
            otv = min(otv, i - min(p2, p1) + 1)
            p3 = i
    if otv > len(s):
        print(0)
    else:
        print(otv)

tt = int(input())
while tt > 0 :
	tt -= 1
	s = input()
	n = len(s)
	o, t, r= [0] * n, [0] * n, [0] * n
	o[0] = t[0] = r[0] = -1
	ans = n + 1
	for i in range(n) :
		if i > 0 :
			o[i] = o[i - 1]
			t[i] = t[i - 1]
			r[i] = r[i - 1]
		if s[i] == '1' :
			o[i] = i
		elif s[i] == '2' :
			t[i] = i
		else :
			r[i] = i
		mn = min(o[i], t[i], r[i])
		if mn > -1 :
			ans = min(ans, i - mn + 1)
	if ans == n + 1:
		ans = 0
	print(ans)

import sys

readline = sys.stdin.readline
read = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    s = list(map(lambda x:int(x) - 1, list(ns())))
    n = len(s)
    l = [3*n]*3
    ans = 3*n
    for i in range(n-1, -1, -1):
        l[s[i]] = i
        ans = min(ans, max(l) - i + 1)
    print(ans if ans <= n else 0)
    return


# solve()

T = ni()
for _ in range(T):
    solve()


t = int(input())
for _ in range(t):
    s = input()
    a = -1
    b = -1
    c = -1
    mn = 10 ** 9
    for i in range(len(s)):
        if s[i] == '1':
            a = i
        elif s[i] == '2':
            b = i
        else:
            c = i
        if a != -1 and b != -1 and c != -1:
            mn = min(mn, max(a, b, c) - min(a, b, c) + 1)
    if mn == 10 ** 9:
        print(0)
    else:
        print(mn)



def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
for case_num in range(t):
    s = input()
    cnt = dict()
    cnt['1'] = 0
    cnt['2'] = 0
    cnt['3'] = 0
    ans = len(s) + 1
    l = 0
    r = -1
    while r < len(s):
        while cnt['1'] == 0 or cnt['2'] == 0 or cnt['3'] == 0:
            r += 1
            if r >= len(s):
                break
            cnt[s[r]] += 1
        if cnt['1'] > 0 and cnt['2'] > 0 and cnt['3'] > 0:
            ans = min(ans, r - l + 1)
        cnt[s[l]] -= 1
        l += 1
    print(ans if ans <= len(s) else 0)


for nt in range(int(input())):
	s=input()
	n=len(s)
	arr=[]
	c=1
	prev=s[0]
	for i in range(1,n):
		if s[i]==prev:
			c+=1
		else:
			arr.append((prev,c))
			prev=s[i]
			c=1
	arr.append((prev,c))
	# print (arr)
	m=10**9
	for i in range(len(arr)-2):
		if arr[i][0]!=arr[i+1][0] and arr[i][0]!=arr[i+2][0]:
			m=min(m,arr[i+1][1]+2)
	if m==10**9:
		print (0)
	else:
		print (m)

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


for _ in range(val()):
    i = j = 0
    s = li3()
    n = len(s)
    a = b = c = 0
    ans = float('inf')
    # print(s)
    while j < len(s):
        if s[j] == 1:a += 1
        elif s[j] == 2:b += 1
        else:c += 1
        if a and b and c:
            while i < j:
                if s[i] == 1:
                    if a > 1:a -= 1
                    else:break
                elif s[i] == 2:
                    if b > 1:b -= 1
                    else:break
                else:
                    if c > 1:c -= 1
                    else:break
                i += 1
            ans = min(ans,j - i + 1)
        j += 1
    if ans != float('inf'):
        print(ans)
    else:print(0)