#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 - 1) / 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);
    }

    if (find_character(0, n1)) 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;
}