传统题 1000ms 256MiB

Runtime Error

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

12k1\over 2^k,22k2\over 2^k,32k3\over 2^k,...,n2kn\over 2^k

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

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

例如:646\over 4的最简形式是323\over 2, 626\over 2的最简形式是313\over 1.

Format

Input

第一行包含一个整数T(1T1051\leq T\leq 10^5)--测试案例的数量。

每个测试用例由一行组成,包含2个整数n(1n1091\leq n\leq 10^9)和k(0k1090\leq k\leq 10^9)。

Output

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

Samples

2
5 0
5 1
15
12

样例解释

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

121\over 2111\over 1323\over 2212\over 1525\over 2

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

2022ACM新生积分赛 Round #3

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2022-10-29 13:00
结束于
2022-10-29 18:00
持续时间
5 小时
主持人
参赛人数
70