Hide

Problem C
Ocean Monument

/problems/oceanmonument/file/statement/en/img-0001.png
Elder Guardian

Steve has stumbled across an ocean monument and would like to raid it. He has put on his best set of armor and brought his favorite trident in search of the rumored sponge room.

The monument is protected by a lot of angry guardians and elder guardians. The mobs are very strong, and Steve has found that each time he enters the monument, he can either kill up to two guardians or exactly one elder guardian before having to retreat to heal. However, each time he retreats, a new guardian spawns in the monument. Luckily, elder guardians never respawn.

Steve will need to slay all the mobs in the monument before it is safe for him to loot it. He wants to kill the mobs in an optimal way, such that he minimizes the total number of trips to the monument required. Write a program that will help him figure out the number of such optimal orders he can choose from.

For example, if there were initially $1$ guardian and $2$ elder guardians in the monument, there are $2$ optimal orders that minimize the number of trips required: he could either kill an elder guardian in both of the first two trips and kill two guardians in the next two trips, or he could kill an elder guardian in the first trip, kill two guardians in the second trip, kill the second elder guardian in the third trip, and kill two guardians in the fourth trip.

Input

The first line contains an integer $1 \leq t \leq 500$, giving the number of test cases to follow. Each case consists of one line containing two integers $0 \leq g,e \leq 20$, the number of guardians and elder guardians respectively that are in the monument the first time Steve enters.

Output

For each test case, output one line containing a single number, the number of optimal orders in which Steve can kill the mobs.

Sample Input 1 Sample Output 1
3
1 2
1 5
2 3
2
42
14
CPU Time limit 1 second
Memory limit 1024 MB
Author
Rishi Sankar
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in