S

s.cpp

#include<bits/stdc++.h>
using namespace std;
int lps(string a)
{
   int n = a.size();
   int length = 0;
   bool dp[n][n];
   for(int i=0;i<n;i++)
   {
      for(int j=0;j<n;j++)
      {
         dp[i][j] = 0;
      }
   }
   for(int i=0;i<n;i++)
   {
      dp[i][i] = 1;
      length = 1;
   }
   for(int i=0;i<n-1;i++)
   {
      if(a[i]==a[i+1])
      {
         dp[i][i+1] = 1;
         length = 2;
      }
   }
   for(int k=3;k<=n;k++)
   {
      for(int i=0;i<n-k+1;i++)
      {
         int j = i + k - 1;
         if((dp[i+1][j-1] == 1) && (a[i] == a[j]))
         {
            dp[i][j] = 1;
            length = max(length,k);
         }
      }
   }
   return length;
}
long long int isprime(long long int n)
{
   //printf("%lld\n",n);
   if(n == 1)
   {
      printf("NOT PRIME\n");
      return 0;
   }
   long long int srt = sqrt(n);
   for(long long int i=2;i<=srt;i++)
   {
      if(n%i==0)
      {
         printf("NOT PRIME\n");
         return 0;
      }
   }
   printf("PRIME\n");
}
int main()
{
   long long int t;
   scanf("%lld",&t);
   while(t--)
   {
      string s;
      cin >> s;
      isprime(lps(s));
   }
   return 0;
}