3178: 次元LAB

时间限制:1000 ms 内存限制:128 MB
上传者:
提交:71 通过:7

题目描述

次元LAB来啦!

马上就要召开音乐节,主办方邀请了 $n$ 位嘉宾,为了确定演出顺序,$n$ 位嘉宾围成一圈,嘉宾间进行投票,nakotanmaru(简称nako)作为嘉宾之一,嘉良想要将她安排在最后一个节目作为压台节目!因此设置了特定的投票规则。
假设每个嘉宾只表演一个节目,每个节目只需要一个嘉宾来表演,投票规则如下:
1.将 $n$ 位嘉宾进行编号为 $1,2,3,...,n$,初始大家都在投票区。
2.投票从 $1$ 开始,按标号顺序投票,每个嘉宾投票完立刻公布自己投票内容,因此每个嘉宾一定会投票。
3.在任何时候,一名嘉宾有了 $k$ 票,那么这名嘉宾将会走到确定区,并且不参与剩下的投票环节。
4.嘉宾只能投向当前情况下自己右手边的嘉宾(假设主办方邀请了 $5$ 个嘉宾,当前剩余嘉宾为 $1,3,5$,如果现在轮到 $1$ 投票,$1$ 只能投给 $3$;如果现在轮到 $3$ 投票,$3$ 只能投票给 $5$;如果现在轮到 $5$ 投票,$5$ 只能投票给 $1$)。
5.演出顺序根据走到确定区的顺序确定,最先到确定区的嘉宾第一个表演,最后到确定区的嘉宾倒数第二个表演。
6.投票一直进行,直到当投票区只有 $1$ 名嘉宾时,此时,投票结束,投票区的最后 $1$ 名嘉宾将会作为压台节目的表演者!
为了满足嘉良的愿望——让nako表演压台节目,他想知道,排座位时需要将nako座位设置为多少号才可以满足自己的愿望。
换种说法,当nako座位号为多少时,她会表演压台节目?

输入格式

第一行一个正整数 $T$,表示数据组数。
对于每组数据:
一行两个正整数 $n,k$,代表总人数和上台表演所需的投票数。

输出格式

对于每组数据:
一行一个正整数 $p$,代表nako的座位号为 $p$ 时,会表演压台节目。

输入样例 复制

2
10 1
1000000000 1000000000

输出样例 复制

5
926258177

数据范围与提示