409653: GYM103660 F Sum of Numerators

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 $$$T(1\le T\le 10^5)$$$ — the number of test cases.

Each test case consists of one line containing $$$2$$$ integers $$$n(1\le n\le 10^9)$$$ and $$$k(0\le k\le 10^9)$$$.

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

2
5 0
5 1

15
12

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

$$$$$$ \frac{1}{2}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{5}{2} $$$$$$

The sum of numerators is $$$1+1+3+2+5=12$$$.