gistfile1.txt

#include<iostream>
#include<string>
#define INF 2000000000
#define MAX 2000010
using namespace std;

int Z, pi[MAX], n, range[MAX], S[MAX];
string lyr, result;

void load_data();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  cin >> Z;
  while(Z--) {
    load_data();
    calculate();
    print_data();
  }
  return 0;
}

void load_data() {
  cin >> lyr;
}

void calculate_pi() {
  string tmp = 'a' + lyr;

  int t = 0;
  pi[0] = pi[1] = 0;

  for (int i = 2; i <= n; i++) {
    while (t > 0 && tmp[t + 1] != tmp[i]) t = pi[t];
    if (tmp[t + 1] == tmp[i]) t++;
    pi[i] = t;
  }
}

string min_cover_word() {
  if (lyr.length() == 1) return lyr;

  for (int i = 1; i <= n; i++) range[i] = S[i] = i;

  for (int i = 2; i <= n; i++) {
    if (pi[i] > 0 && range[S[pi[i]]] >= i - S[pi[i]]) {
      S[i] = S[pi[i]];
      range[S[pi[i]]] = i;
    }
  }

  int x = S[n];
  return (x == 2 && lyr[0] == lyr[1]) ? lyr.substr(0, 1) : lyr.substr(0, x);
}

void calculate() {
  n = lyr.length();
  calculate_pi();
  result = min_cover_word();
}

void print_data() {
  cout << result << endl;
}