At East West University there are an infinite number of boys and girls in number. You have \(a\) amount of dairy milk chocolates and \(b\) amount of KitKat chocolates. However, you've suddenly developed a craving for Snickers chocolates. Your goal is to distribute all the dairy milk chocolates and half of the Snickers to boys, while all the KitKats and half of the Snickers are reserved for girls.

Basically, a boy is happy:

1. If he gets no chocolate.
2. Or, the same amount of Dairy Milk as other boys who got Dairy Milk, and the same amount of Snickers as other boys who got Snickers.

Likewise, a girl is happy:

1. If she gets no chocolate.
2. Or, the same amount of KitKats as other girls who got KitKats, and the same amount of Snickers as other girls who got Snickers.

Your aim is to ensure that no one is left sad, and you want to distribute chocolates to as many individuals as possible. Determine the minimum number of Snickers chocolates you need to purchase to achieve this goal.

The first line contains a single integer \(t\) \((1 \leq t \leq 10^5)\) — the number of test cases.
The first line of each test case contains two integers \(a, b\) \((1 \leq a, b \leq 10^9)\)  — described in the statement. 

For each test case, print a single integer — described in the statement.

Input copy	Output copy
3 2 3 6 5 7 7	12 60 14