M. Taim and Zingers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kaito has $$$n$$$ Zingers, and he wants to distribute them between the Kaito kciD team members.

Kaito kciD team consists of 3 members, one of them is greedy Taim.

In order to distribute the $$$n$$$ Zingers between them, Kaito will follow the steps below in order:

— If $$$n$$$ is divisible by $$$3$$$, each of them will get $$$\frac{n}{3}$$$ Zingers.

— Otherwise, if $$$n$$$ is divisible by $$$2$$$, Taim will get $$$\frac{N}{2}$$$ Zingers, and the other two will get the rest.

— Otherwise, Taim will get all the $$$n$$$ Zingers.

Taim can steal at most $$$k$$$ Zingers before Kaito distributes them among the team.

What is the maximum number of Zingers Taim could have (stolen Zingers included)?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

The first line of each testcase consists of two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^9$$$) — the number of Zingers Kaito will give, and the number of Zingers Taim can steal from Kaito before distributing the Zingers.

Output

Output $$$t$$$ lines. For each testcase, print a single integer — the maximum number of Zingers Taim could have.

Example
Input
3
6 1
10 1
20 2
Output
6
5
20