定义 a[l,r]={a[l],a[l+1],a[l+2],...,a[r−1],a[r]}a[l,r]=\{a[l] , a[l+1] , a[l+2], ..., a[r-1] , a[r]\}a[l,r]={a[l],a[l+1],a[l+2],...,a[r−1],a[r]}。
定义 mexmexmex 函数:mex(l,r)=mex(l,r) =mex(l,r)= 不存在于 a[l,r]a[l,r]a[l,r] 内的最小非负整数。
定义 kkk 阶 MexMexMex 数列:
已知 a[i]=Mex(i)a[i]=Mex(i)a[i]=Mex(i),请计算 kkk 阶 Mex(n)Mex(n)Mex(n) 的结果。
输入
第一行输入一个整数 T (1≤T≤105)T \ (1 \leq T \leq 10^5)T (1≤T≤105),表示有 TTT 组数据。
每组数据输入两个整数 n,k (0≤n≤109,1≤k≤109)n,k \ (0 \leq n \leq 10^9,1 \leq k \leq 10^9)n,k (0≤n≤109,1≤k≤109)
输出
输出 kkk 阶 Mex(n)Mex(n)Mex(n) 的结果。
样例
2 1 1 3 5
1 3
来源
广东工业大学 2020 年 ACM 第一次月赛