//Author:Leftist_G / Shunpower
//Cloud Island & Rain Temperature
//May the force be with you and me.
#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define debug puts("--------Chery AK IOI--------");
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define pt puts("")
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define fv(i,p) for(int i=0;i<p.size();i++)
#define ld long double
#define il inline
#define ptc putchar
using namespace std;
const int N=1e5+10;
namespace Shun{
    int lowbit(int x){
        return x&-x;
    }
    template <typename T>
    inline void read(T &x){
       T s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;
            }
            ch=getchar();
        }
       while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
       }
       x=s*w;
    }
    template <typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9){
            write(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace Shun;
vector <int> ck;
int count_pair(int,int,int);
int find_character(int,std::vector<int>);
int guess_palindromicity(int n){
    ck.clear();
    int cpos=-1;
    fr1(i,1,n/2-1){
        int x=count_pair(0,i,n-1-i);
        if(x==3){
            cpos=i;
            continue;
        }
        else if(x==0) return 0;
        else ck.pb(i),ck.pb(n-1-i);
    }
    if(~cpos){//ck.empty() for this
        int x=count_pair(cpos,0,n-1);
        if(x!=3) return 0;
    }
    else{
        int chk=find_character(0,ck);
        if(!chk){
            int x=count_pair(0,n-1,ck[0]),y=count_pair(n-1,ck[0],ck[1]);
            return x==1&&y==1;
        }
        else return 0;
    }
    return !find_character(n-1,ck);
}