Piyush’s crush (let’s call her A) has been struggling with a simple algorithmic problem on HackerEarth. A has managed to develop a recursive solution to the given problem. However, as one can guess, upon submission, it exceeded the time limit for the problem i.e. the verdict received was TLE.

Now, A has asked Piyush for help. Like any other sane man, Piyush took this opportunity. And, due to the nationwide lockdown, he has a lot of free time to solve the problem and impress her. It’s like the universe was with him this time.
But, unlike any other sane man, he did not ask her what the problem statement actually was. He boasted, with pride, that he can optimize her solution without even looking at the problem statement!

And, now, he is stuck.

Can you help him optimize A’s solution?

Here’s the function A shared with Piyush:

int myFunction(int number, int k) {
    if (number >= k)
        return myFunction(number – k, k)
 
    return number;
}

Input:

The first line of the input contains an integer $T$ denoting the number of test cases.

The first and only line of each test case contains two space separated integers – $number$ and $k$, denoting the parameters – $number$ and $k$, that are being passed to $myFuction$ in the provided code snippet.

Output:

For each test case, output the integer that $myFuction$ would return.

Constraints:

$1≤T≤10^5$

$1≤N≤10^{18}$

$1≤k≤10^{18}$