F-Sum of Numerators_第十九届浙大城市学院程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given $2$ integers $n$ and $k$ , and there are $n$ fractions as follows:
$\frac{1}{2^k}, \frac{2}{2^k}, \frac{3}{2^k}, \dots, \frac{n}{2^k}$
Please reduce each fraction to its simplest form and calculate the sum of the numerators.
A fraction $\frac{a}{b}$ is in simplest form if and only if $\gcd (a, b)=1$ , where $\gcd(a,b)$ denotes the greatest common divisor (GCD) of integers $a$ and $b$ . For example, the simplest form of $\frac{6}{4}$ is $\frac{3}{2}$ , and the simplest form of $\frac{6}{2}$ is $\frac{3}{1}$ .

输入描述:

The first line contains an integer  --- the number of test cases.
Each test case consists of one line containing  integers  and .

输出描述:

For each test case, output an integer in a line.

示例1

输入

复制

2
5 0
5 1

输出

复制

15
12

说明

In the second test case of the sample, the simplest form of the  fractions is as follows:

The sum of numerators is .