假设您与两只猫住在一起:A 和 B。两只猫通常都睡觉的地方有 $$$n$$$ 午睡点。
你的猫喜欢睡觉,也喜欢所有这些地方,所以它们每小时循环改变午睡地点:
- Cat A 按顺序改变午睡地点:$$$n, n - 1, n - 2, \dots, 3, 2, 1, n, n - 1, \dots$$$ 换句话说,第一个小时它在原地 $$$n$$$,然后循环递减;
- Cat B 按顺序更改其午睡位置: $$$1, 2, 3, \dots, n - 1, n, 1, 2, \dots$$$ 换句话说,在第一个小时,它在原地 $$$1$$$,然后循环递增。
猫 B 更年轻,因此它们有严格的等级制度:A 和 B 不会躺在一起。换句话说,如果两只猫都想进入 $$$x$$$ 位置,那么 A 占据这个位置,B 移动到顺序中的下一个位置(如果 $$$x < n$$$ 则移动到 $$$x + 1$$$,但如果 $$$x = n$$$ 则移动到 $$$1$$$)。 Cat B 遵循他的命令,因此在 A 释放它后,它不会返回到跳过的位置 $$$x$$$,而是会移动到位置 $$$x + 2$$$ 等等。
计算一下,$$$k$$$ 时猫 B 会在哪里?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$) - 点的数量和小时 $$$k$$$。
输出
对于每个测试用例,打印一个整数 - 猫 B 在 $$$k$$$ 小时睡觉的地点的索引。
示例
输入 #1
7 2 1 2 2 3 1 3 2 3 3 5 5 69 1337
输出 #1
1 2 1 3 2 2 65
注意
在第一个和第二个测试用例 $$$n = 2$$$ 中,所以:
- 在$$$1$$$第一个小时,A 在 $$$2$$$ 现场,B 在 $$$1$$$ 现场;
- 在第 $$$2$$$ 小时,A 移动到 $$$1$$$,B — 移动到 $$$2$$$。
- 在$$$1$$$第一个小时,A 在 $$$3$$$ 现场,B 在 $$$1$$$ 现场;
- 在第$$$2$$$第一个小时,A 移动到$$$2$$$; B想从$$$1$$$移动到$$$2$$$,但是这个位置已被占用,所以它移动到$$$3$$$;
- 在$$$3$$$第一个小时,A移动到$$$1$$$; B 也想从 $$$3$$$ 移动到 $$$1$$$,但是这个位置已被占用,所以它移动到 $$$2$$$。
在第六个测试用例中:
- A 每小时的位置为 $$$[5, 4, 3, 2, 1]$$$;
- B 每小时的位置为 $$$[1, 2, 4, 5, 2]$$$。