UVa 11888 - Abnormal 89's

// UVa 11888 - Abnormal 89's

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

	private static int[] t;

	private static void buildPartialMatchTable(String w) {
		int len = w.length();
		t = new int[len];
		t[0] = 0;
		int i = 2, j = 0;
		t[0] = -1;
		t[1] = 0;
		while (i < len) {
			if (w.charAt(i - 1) == w.charAt(j)) {
				t[i] = j + 1;
				i++;
				j++;
			} else if (j > 0) {
				j = t[j];
			} else {
				t[i] = 0;
				i++;
			}
		}
	}

	public static int KMP(String s, String w) {
		buildPartialMatchTable(w);
		int m = 0, i = 0;
		while (m + i < s.length()) {
			if (w.charAt(i) == s.charAt(m + i)) {
				i++;
				if (i == w.length())
					return m;
			} else {
				m += i - t[i];
				if (i > 0)
					i = t[i];
			}
		}
		return s.length();
	}

	public static void main(String[] args) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(
					System.in));
			int cases = Integer.parseInt(reader.readLine());

			for (; cases > 0; cases--) {
				String s = reader.readLine();
				if (s.length() == 0) {
					System.out.println("simple");
					continue;
				} else if (s.length() == 1) {
					System.out.println("palindrome");
					continue;
				}
				String r = (new StringBuilder(s)).reverse().toString();
				String ss = (new StringBuilder(s)).append(s).substring(1,
						s.length() * 2 - 1);

				int ssKmpResult = KMP(ss, r);
				if (ssKmpResult + 1 < s.length())
					System.out.println("alindrome");
				else {
					if (s.equals(r))
						System.out.println("palindrome");
					else
						System.out.println("simple");
				}

			}
		} catch (Exception ex) {

		}
	}

}