#include <bits/stdc++.h>
using namespace std;

inline int random_value(int min, int max) {
     static mt19937 random(chrono::system_clock::now().time_since_epoch().count());
     return uniform_int_distribution<int>(min,max)(random); }

unordered_map<int,int> dp; int used; 

inline int solve(int n, int p = 0) {
    if (n == 1)
        return 1-p; 
    if (n == 2 or n&1)
        return p; 
    auto it = dp.find(n);
    if (it != dp.end()) 
        return ++used, it->second^p;
    int ans = 1-p;
    for (int y, x = 2; x*x <= n; ++x)
        if (n%x == 0) {
            if (x&1 and solve(n/x,1-p) == p) {
                ans = p; break; }
            if (y = n/x, y > x and y&1 and solve(n/y,1-p) == p) {
                ans = p; break; } }
    dp[n] = ans^p; 
   return ans; }

int main() {
    for (int i = 0; i < 1000000; ++i)
    	solve(random_value(1,1000000000)); 
	cout << "dp value used " << used << " time(s)"; }