1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <string>
  6 using namespace std;
  7 #define N 1000005
  8 string s;
  9 string le, ri, mi, temp;
 10 int nxt[N];
 11 
 12 void make_next(string s)
 13 {
 14     memset(nxt, 0, sizeof(nxt));
 15     int l = s.size();
 16     int j = -1, i = 0;
 17     nxt[0] = -1;
 18     while(i < l) {
 19         if(j == -1 || s[j] == s[i]) {
 20             j++; i++;
 21             nxt[i] = j;
 22         } else {
 23             j = nxt[j];
 24         }
 25     }
 26 }
 27 /*
 28 前面的串和后面的串匹配的时候只能前后缀匹配传入0
 29 前面的串和中间的串匹配或者后面的串和中间的串匹配传入1
 30 */
 31 int kmp(string s, string str, int flag)
 32 {
 33     int l = s.size(), L  = str.size();
 34     make_next(s);
 35     int i = 0, j = 0;
 36     while(i < L && j < l) {
 37         if(j == -1 || s[j] == str[i]) {
 38             i++; j++;
 39             if(flag && j==l) return j;
 40         } else {
 41             j = nxt[j];
 42         }
 43     }
 44     if(i == L) return j;
 45     return 0;
 46 }
 47 
 48 int main()
 49 {
 50     int t;
 51     cin >> t;
 52     while(t--) {
 53         s.clear();
 54         temp.clear();
 55         mi.clear();
 56         le.clear();
 57         ri.clear();
 58         cin >> s;
 59         int len = s.size();
 60         if(len < 3) {
 61             puts("0"); continue;
 62         }
 63         for(int i = 0; i < len; i++) {
 64             if(i <= len/3 - 1) {
 65                 le += s[i];
 66             } else if(i >= len*2/3) {
 67                 ri += s[i];
 68             } else {
 69                 mi += s[i];
 70             }
 71         }//将一条串拆成三部分
 72 
 73         int lo = kmp(le, ri, 0);
 74         if(lo == 0) {
 75             puts("0"); continue;
 76         }
 77         //lo是公共前后缀长度
 78 //        }
 79         for(int i = 0; i < ri.size()-lo; i++)
 80             mi += ri[i];
 81 
 82         for(int i = lo; i < le.size(); i++) {
 83             temp += le[i];
 84         }
 85 
 86         int l = le.size(), r = ri.size();
 87 
 88         ri.erase(0, r - lo);
 89         le.erase(lo, r);
 90         temp += mi;
 91 
 92         int ans = 0;
 93         int k = kmp(le, temp, 1);
 94         int g = kmp(ri, temp, 1);
 95         ans = min(k, g);
 96 
 97         cout << ans << endl;
 98     }
 99     return 0;
100 }