H3.cpp

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

int Z, pi[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() {
  pi[0] = -1; int t = -1;
  for (int i = 1; i <= lyr.length(); i++) {
    while (t >= 0 && lyr[t+1] != lyr[i]) t = pi[t];
    t++;
    pi[i] = t;
  }
}

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

  int range[MAX], S[MAX];

  for (int i = 1; i < lyr.length(); i++) {
    range[i] = S[i] = i+1;
  }

  for (int i = 1; i < lyr.length(); i++) {
    if (pi[i] > 0 && i-range[S[pi[i]]] < S[pi[i]]) {
      S[i] = S[pi[i]];
      range[S[pi[i]]] = i;
    }
  }

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

void calculate() {
  calculate_pi();
  result = min_cover_word();
}

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