显然这个博弈的流程是：双方审核其它不重要的论文（显然此时我们只需要关心移除了几篇论文）直到论文抵达前 $k$ 个位置；然后进行一轮关键的操作，之后要么游戏结束，要么论文被扔到了后 $k$（或者 $k-1$）个位置中的一个。把这样的一个过程称作“一轮”。

首先特判论文活不过第一轮的情况。然后我们发现当论文在前 $k$ 个位置的时候，投稿人的策略肯定是：尝试把论文扔到最后面的位置使得它下一轮能活下来；否则直接发表，获得分数。

不妨假设第一轮已经结束了，此时剩下 $n'$ 篇论文，关键的论文在后 $k$ 个位置当中。现在令 $\bmod\ 2k$ 的值在 $1\sim k$ 中的位置为坏位置，其他位置为好位置，显然坏位置和好位置都以长度为 $k$ 的段的形式交替出现。那我们肯定希望论文落在一个好位置。显然只存在至多一个好的段使得论文可能在里面出现。并且我们实际上不关心它在这个段中的位置——因为下一轮的操作次数是一样的。

先不考虑没有好位置（此时唯一的决策是立即结束）的情况。

我们发现可以只用 $n$ 来描述一轮开始时的状态。之后我们考虑博弈的过程。这个博弈一定进行了 $2d$ 轮，其中 $d=\left\lfloor\frac{n+k}{2k}\right\rfloor$。在这 $2d$ 轮的最后一轮中，投稿人审到了自己的论文，选择开始新的一轮或者直接结束游戏，这样就转移到了下一个“一轮开始时”的状态。

每一轮可以选择移除一篇论文或者啥也不干。那么这个转移可以画成一个三角形：

    a
   b c
  d e f
 g h i j
k l m n o

这里展示了 $d=2$ 的情况。由于第奇数次操作是审稿人进行的，第偶数次操作是投稿人进行的，这个三角形自底向上的转移是 $\max$ 和 $\min$ 交替。

猜测双方都会把这个转移路径控制在中间——实际上这个猜测是对的。事实上，我们有 $a = \max(m,\min(l,n))$，或者说 $f(n) = \max(f(n-d),\min(f(n-d-1),f(n-d+1)))$。

证明：任取 $x$，把每个位置上的值按照 $\ge x$ 和 $< x$ 分成 $1$ 和 $0$ 两类，那么 $\max$ 和 $\min$ 就变成了按位或和按位与。之后对着中心附近几个位置 $0$ 和 $1$ 的连续段情况分讨即可。后面的结论也都是用类似的方法证出来的。

但是此时需要计算的状态数量还是很多。为了优化转移，考虑一种比较特殊的情况：$n-d-1, n-d, n-d+1$ 对应的下一步的 $d'$ 都相同。此时把它们的式子展开之后，会发现 $f(n) = f(n-d)$。这是一个非常强的结论。在第一个代码块后面有关于这个结论的进一步说明。

那么问题来了：如果 $d'$ 不同怎么办？而且不是所有状态都是合法的。

例如说，如果 $2k\mid n + k$ 或者 $n\le k$，那么这个状态一定不合法。而如果 $2k\mid n + k + 1$，那么它的上一步转移不能移除论文——因为这里的后 $k-1$ 个位置都是坏位置，如果上一步这么做，论文就必须放到这 $k-1$ 个位置当中。

那么好消息来了：如果你手算一下这两种特殊情况可能影响到的 $n$，会发现它们其实是一种情况，也就是 $(n-d)\bmod 2k$ 在 $k$ 附近。

这种情况下，有一些转移路径是不合法的。例如，对于上面 $d=4$ 的情况来说，一种可能的情况是 $(h,l),(h,m),(i,m)$ 三条转移不合法。这种情况下 $m$ 对应的状态满足 $2k\mid n+k$，$l$ 对应的状态满足 $2k\mid n+k+1$。

那么这里需要做一些特判。最后的结论是：如果 $(n-d)\ \bmod 2k$ 的值是 $k$ 或者 $k-1$，或者 $n-d\le k$，那么审稿人一定能迫使投稿人走到非法转移上，必须发表自己的论文；否则，永远有 $f(n) = f(n-d)$。

当然，第一轮是投稿人先操作的，并且论文的位置比较随机。不过这不是问题，因为可以枚举他的第一步操作，然后根据论文位置计算 $d$，再用上面的方法求解。代码中的实现方式略有不同，不过本质上是类似的。

特判一下 $k=1$ 之后就可以得到下面这个实现：

ll solve(ll n){
    ll ans=1,now=n;
    while(1){
        ll d=(now+k)/(2*k);
        if ((now-d)%(2*k)==k||(now-d)%(2*k)==(k-1)||now-d<=k){
            return ans;
        }
        now-=d;++ans;
    }
    return ans;
}

现在它的复杂度还有点爆，原因是 $k$ 大的时候 $d$ 非常小。但此时我们发现：每删 $2k$ 个数才能遇到一个非法状态，也就是说我们可以把若干轮当作一轮看待，因为中间不可能遇到任何非法状态。实际上，这也就是之前 $f(n) = f(n-d)$ 的原因。

这启发我们按照 $d=\left\lfloor\frac{n+k}{2k}\right\rfloor$ 分段，把每一段内的多轮转移合并成一轮。

然后就做完了。时间复杂度显然 $\mathcal{O}(n^{\frac 2 3})$ 但好像其实是根号的，懒得认真分析了，反正能过。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1000007;
ll T,n,m,k;
ll solve(ll n){
    ll ans=1,now=n;
    while(1){
        ll d=(now+k)/(2*k),L=d*(2*k)-k+1;
        if (now>L+1){
            ll k=(now-(L+1))/d;
            now-=d*k;ans+=k;
        }
        if ((now-d)%(2*k)==k||(now-d)%(2*k)==(k-1)||now-d<=k){
            return ans;
        }
        now-=d;++ans;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k>>m;--m;
        if ((m/k)&1){
            cout<<"0\n";continue;
        }
        if (k==1){
            cout<<(1+(m==0&&n%2==0))<<"\n";continue;
        }
        ll u=n-m/(2*k);
        if (u%(2*k)==k||u<=k){
            cout<<"1\n";continue;
        }
        else if (u%(2*k)==k+1){
            cout<<solve(u)+1<<'\n';continue;
        }
        else if (u%(2*k)==k-1&&m>k){
            cout<<solve(u-1)+1<<'\n';continue;
        }
        cout<<max(solve(u),solve(u-1))+1<<'\n';
    }
    return 0;
}