// Source: https://usaco.guide/general/io

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


int query(int x, int y);



int solve(int n){
    vector<array<int, 3>> a;
    bool c=false;
    bool b=false;
    int x, y;
    for(int i=2;i<=n/2;i++){
        if(query(0, i)){
            x=i;
            b=true;
        }
        if(query(0, n-i)){
            y=n-i;
            c=true;
        }
    }
    if(!b && !c){
        return 1*n+n-1;
    }
    if(b && !c){
        return x*n+n-1;
    }
    if(c && !b){
        return 1*n+y;
    }
    if(x==y){
        return x;
    }
    if(abs(x-y)==1){
        return x;
    }
    return x*n+y;
}