谁能组建一个完美的Codeforces 122C团队？

本文共计855个文字，预计阅读时间需要4分钟。

您可能已经知道，标准的ICPC队伍由三名成员组成。然而，完美的队伍有更多限制。一名学生可能有特殊专长：程序员或数学家。她/他可以没有专长，但必须满足以下条件：

You may have already known that a standard ICPC team consists of exactly three members. The perfect team however has more restrictions. A student can have some specialization: coder or mathematician.She/he can have no specialization, but can‘t have both at the same time.

So the team is considered perfect if it includes at least one coder, at least one mathematician and it consists of exactly three members.

You are a coach at a very large university and you know thatc">ccof your students are coders,m">mmare mathematicians andx">xxhave no specialization.

What is the maximum number of full perfect teams you can distribute them into?

Note that some students can be left without a team and each student can be a part of no more than one team.

You are also asked to answerq">qqindependent queries.

Input

The first line contains a single integerq">qq(1≤q≤104">1≤q≤1041≤q≤104) — the number of queries.

Each of the nextq">qqlines contains three integersc">cc,m">mmandx">xx(0≤c,m,x≤108">0≤c,m,x≤1080≤c,m,x≤108) — the number of coders, mathematicians and students without any specialization in the university, respectively.

Note that the no student is both coder and mathematician at the same time.

Output

Printq">qqintegers — thei">ii-th of them should be the answer to thei">iiquery in the order they are given in the input. The answer is the maximum number of full perfect teams you can distribute your students into.

Example

Input

6 1 1 1 3 6 0 0 0 0 0 1 1 10 1 10 4 4 1 Output

1 3 0 0 1 3

Note

In the first example here are how teams are formed:

1. the only team of 1 coder, 1 mathematician and 1 without specialization;
2. all three teams consist of 1 coder and 2 mathematicians;
3. no teams can be formed;
4. no teams can be formed;
5. one team consists of 1 coder, 1 mathematician and 1 without specialization, the rest aren‘t able to form any team;
6. one team consists of 1 coder, 1 mathematician and 1 without specialization, one consists of 2 coders and 1 mathematician and one consists of 1 coder and 2 mathematicians.

题接：题目描述的意思就是 x个a y个b, z个c ，在a和b中至少选择一个,最终凑成3个数，c有选不选都可以，问，，最多能有多少种选择？

FS: 马虎，，，下次做这种多中过程的题目时，可以把每个过程的做法以及思路写下来。

思路： 因为z可有可无，所以我们首先要考虑z，如果z比x或者y任何一个数大的话，那就直接输出x和y的最小值。否则优先使用z即答案ans+=z，然后x和y的个数都减去个z，在考虑x和y较大的那个，求差y1，如果y>x和y最小值；

那么输出abs+=x和y的最小值，否则 用掉y 这时x=y=x-y1，，答案为ans+=(x+x)/3‘

#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int x,y,z; scanf("%d%d%d",&x,&y,&z); int x1=min(x,y); int x2=max(x,y); if(x1<=z) printf("%d\n",x1); else { int ans=0; ans=z; x1=x1-z; x2=x2-z; int y; y=x2-x1; if(y>=x1) cout<<x1+ans<<endl; else { ans+=y; x1-=y; cout<<ans+(x1+x1)/3<<endl; } } } return 0; }