As students of  LNMIIT Pinkesh and his friends like elections a lot. For the post of the president, there are two parties, A and B.

There are n supporters of A and m supporters of B.Among those n students there are k students who have friendship with k students of B’s supporters.

There is a rule in their friendship that if a person has a friendship with another one then both of them should vote for the same person. Otherwise their Friendship will be broken. Also in these k friendships, all the friendships are between supporters of A and supporters of B.

One of Pinkesh’s friend asks him to solve a problem that he has to maximize the votes of the party which will have either less or equal votes than other party, such that there are no broken friendships.

Note : Two parties can have same votes

As Pinkesh is busy in some work he has asked you to solve the problem.

INPUT:

The first line of the input contains a single integer t denoting the number of test cases. The description of t test cases follows.

The first line of each test case contains integers n , m , k.

CONSTRAINTS: 

1<= t <= 2*10⁵

1<= n <= 10¹⁸

1<= m <= 10¹⁸

0<= k <= min(n,m)

OUTPUT:

For each test case, print a single line containing one integer maximum possible votes of the party with less votes.