#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 10000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
ll findGap(int t, int n)
{
if(t==1LL)
{
deque<ll> dq;
vector<pair<ll, ll> > v;
ll l = 1LL;
ll r = (ll)1e18;
for(int i = 1;i<=(n+1)/2;i++)
{
ll mini, maks;
MinMax(l, r, &mini, &maks);
v.pb(make_pair(mini, maks));
l = mini + 1;
r = maks - 1;
}
for(int i = (n+1)/2-1;i>=0;i--)
{
if(v[i].first!=v[i].second)
{
dq.pb(v[i].second);
dq.push_front(v[i].first);
}
else
{
dq.pb(v[i].first);
}
}
ll maks = 1;
for(int i = 1;i<len(dq);i++)
{
maks = max(maks, dq[i] - dq[i-1]);
}
return maks;
}
else
{
ll d = (ll)(1e18)/n;
ll rem = (ll)(1e18)%n;
ll l = 1;
ll ans = 1;
vector<pair<ll, ll> > v;
for(int i = 0;i<n;i++)
{
ll mini, maks, w;
w = d;
if(i < rem) w++;
ll r = l + w - 1;
MinMax(l, r, &mini, &maks);
v.pb(make_pair(mini, maks));
l = r + 1;
}
for(int i = 1;i<len(v);i++)
{
ans = max(ans, v[i].first - v[i-1].second);
}
return ans;
}
}
