You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given a string S composed only of uppercase English letters. Your task is to find the minimum-length contiguous substring of S that can be transformed into the target string "IEEELUSBCHAPTER". A transformation consists of two operations:

• Erase: You may remove any number of characters from the chosen substring.
• Rearrange: You can reorder the remaining characters in any order.

A substring is defined as a sequence of consecutive characters from S. For example, in "BANANA", "BAN", "ANA", and "NAN" are valid substrings, but "BNA" and "BNN" are not valid.
If no contiguous substring can be transformed into "IEEELUSBCHAPTER", output -1.

Input

• The first line contains an integer T (1 ≤ T ≤ 20), the number of test cases.
• Each of the next T lines contains a single string S (1 ≤ |S| ≤ 10⁵), consisting of uppercase English letters.

Output

For each test case, print a single integer for each case: the minimum length of a contiguous substring that can be transformed into "IEEELUSBCHAPTER" by erasing and rearranging characters. If no such substring exists, print -1.

Sample

3
ABCIEEELUSBCHAPTER
LVBAAHHPZETLIRSEUCETEGCXN
LEADINGUNIVERSITYSYLHET

15
19
-1