Description

小金金给了你2个整数n和k，有n个分数，如下所示。

$1\over 2^k$,$2\over 2^k$,$3\over 2^k$,...,$n\over 2^k$

小金金想将每个分数简化为最简形式，并计算分子之和。请问你能帮帮他吗。

当且仅当gcd(a,b)=1时，分数$a\over b$才是最简形式，其中gcd(a,b)表示整数a和b的最大公约数(GCD)。

例如：$6\over 4$的最简形式是$3\over 2$, $6\over 2$的最简形式是$3\over 1$.

Format

Input

第一行包含一个整数T（$1\leq T\leq 10^5$）--测试案例的数量。

每个测试用例由一行组成，包含2个整数n（$1\leq n\leq 10^9$）和k（$0\leq k\leq 10^9$）。

Output

对于每个测试用例，在一行中输出一个整数。

Samples

2
5 0
5 1

15
12

样例解释

在样本的第二个测试案例中，5个分数的最简单形式如下。

$1\over 2$，$1\over 1$，$3\over 2$，$2\over 1$，$5\over 2$

分子之和为1+1+3+2+5=12。