ACMT - Acm Teams

Engineer Ahmed Sror one of the best coaches. He picks team members by using two ways.

First one that the optimal team of three people should consist of one experienced participant and two newbies. Thus, each experienced participant can share the experience with a large number of people.

Second one that the optimal team should have two experienced members plus one newbie. Thus, each newbie can gain more knowledge and experience.

All the teams during the training session should belong to one of the two ways described above. Furthermore, they agree that the total number of teams should be as high as possible.

There are E experienced members and N newbies on the training session. Can you calculate what maximum number of teams can be formed?

Input

The first line of the input contains a single integer corresponding to number of test cases t (1 ≤ t ≤ 10) ,The second line contains two integers E and N (0 ≤ E, N ≤ 5·105) — the number of experienced participants and newbies that are present at the training session.

Output

For each test case print a single integer representing the maximum number of teams that can be formed.

Example

Input:
2
2 6
4 5

Output:
2
3

Note Let's represent the experienced players as XP and newbies as NB.

In the first test the teams look as follows: (XP, NB, NB), (XP, NB, NB).
In the second test sample the teams look as follows: (XP, NB, NB), (XP, NB, NB), (XP, XP, NB).


Added by:atef
Date:2015-04-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2020-04-15 15:50:42
remember a and b should be greater than or equal to 1 and not zero :)
2019-02-25 13:54:03
Can anyone check my solution?
My solution ID is 23295393.
2018-09-18 00:34:04
dont try hard!!
2018-08-05 12:18:43
AC in one go
2018-06-13 17:15:07
Linear Programming problem.. Game Theoey :P
Beware of an edge case!
2018-06-03 15:37:18
cake-walk :)
2017-08-06 07:56:25
Not running on test case 7. Please help.
2017-07-19 15:19:00
Just hit and trial method,make sequence for inputs and outputs
2017-06-12 12:22:29
apply greedy.
2017-03-01 18:26:55
Damn easy....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.