前缀和

题号：NC296024
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红有一个由正整数组成的数组 $a$ ，但是她没有告诉你数组中的元素具体是什么，你只知道这个数组的元素各不相同，且其前缀数组 $s$ 对于给定的一个 $x$ ，其任意一项均满足：
$\hspace{23pt}\bullet\,$ 对于数组的第 $k$ 个元素，当 $\lfloor \tfrac{k}{x} \rfloor$ 为偶数时， $s_k = a_1 + a_2 + \cdots + a_k$ 也是偶数；
$\hspace{23pt}\bullet\,$ 对于数组的第 $k$ 个元素，当 $\lfloor \tfrac{k}{x} \rfloor$ 为奇数时， $s_k = a_1 + a_2 + \cdots + a_k$ 也是奇数。
$\hspace{15pt}$ 除此之外，你还知道这个数组是满足条件的所有数组中字典序最小的。小红现在来问你，这个数组中第 $p$ 个元素是多少，你能快速的回答她吗？

【名词解释】
$\hspace{15pt}$ 字典序：从两个数组的第一个元素开始逐个比较，直到找到第一个不同的元素，较小元素所在的数组的字典序较小。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入两个整数 ，代表题目中给定的  以及询问的位置。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示数组中第  个元素是多少。

示例1

输入

复制

2
3 4
2 5

输出

复制

6
6

说明

对于 ，我们可以找到，符合题意的字典序最小的数组为 ，因此第  个元素为 。