#include <bits/stdc++.h>
using namespace std;
extern int count_pair(int, int, int);
extern int find_character(int, std::vector<int>);
int guess_palindromicity(int n){
    vector <int> n1, n2;

    for (int i = 1; i < n / 2; ++ i){
        int gg = count_pair(0, i, n - 1 - i);
        if (!gg) return 0;
        if (gg == 1) n1.push_back(i);
        else n2.push_back(i);
    }

    //cout << n1.back() << endl;

    vector <int> dhs = n1;
    for (int i : n1) dhs.push_back(n - i - 1);

    if (find_character(0, dhs)) return 0;

    if (n2.size()){
        int i = n2.back();
        if (count_pair(n - 1, n - 1 - i, i) == 1) return 0;
        return 1;
    }
    int i = n1.back();
    int gg = count_pair(0, n - 1, i);
    if (!gg) return 0;
    if (gg == 3) return 1;
    if (count_pair(n - 1, i, n - i - 1) == 3) return 0;
    return 1;
}