Codeforces Round 780 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

math

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Vasya and Coins

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya decided to go to the grocery store. He found in his wallet $$$a$$$ coins of $$$1$$$ burle and $$$b$$$ coins of $$$2$$$ burles. He does not yet know the total cost of all goods, so help him find out $$$s$$$ ($$$s > 0$$$): the minimum positive integer amount of money he cannot pay without change or pay at all using only his coins.

For example, if $$$a=1$$$ and $$$b=1$$$ (he has one $$$1$$$-burle coin and one $$$2$$$-burle coin), then:

- he can pay $$$1$$$ burle without change, paying with one $$$1$$$-burle coin,
- he can pay $$$2$$$ burle without change, paying with one $$$2$$$-burle coin,
- he can pay $$$3$$$ burle without change by paying with one $$$1$$$-burle coin and one $$$2$$$-burle coin,
- he cannot pay $$$4$$$ burle without change (moreover, he cannot pay this amount at all).

So for $$$a=1$$$ and $$$b=1$$$ the answer is $$$s=4$$$.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The description of each test case consists of one line containing two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^8$$$) — the number of $$$1$$$-burle coins and $$$2$$$-burles coins Vasya has respectively.

Output

For each test case, on a separate line print one integer $$$s$$$ ($$$s > 0$$$): the minimum positive integer amount of money that Vasya cannot pay without change or pay at all.

Example

Input

5 1 1 4 0 0 2 0 0 2314 2374

Output

4 5 1 1 7063

Note

- The first test case of the example is clarified into the main part of the statement.
- In the second test case, Vasya has only $$$1$$$ burle coins, and he can collect either any amount from $$$1$$$ to $$$4$$$, but $$$5$$$ can't.
- In the second test case, Vasya has only $$$2$$$ burle coins, and he cannot pay $$$1$$$ burle without change.
- In the fourth test case you don't have any coins, and he can't even pay $$$1$$$ burle.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2024 04:58:17 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|