Chef has two piles of stones with him, one has n1 stones and the other has n2 stones. Fired up by boredom, he invented a game with the two piles.

Before the start of the game Chef chooses an integer m.

In the j-th move: 

-  He chooses a number xj such that 1 ≤ xj ≤ m, and removes xj stones from both the piles (this is only possible when both the piles have ≥ xj stones).
-  The number chosen must be unique over all the moves in the game. That is, for all k < j, xj ≠ xk. 

The game stops when Chef is unable to make any more moves.

Chef wants to make the moves in such a way that the sum of the number of stones remaining in the two piles is minimized. Please help Chef find this.

-----Input-----
- The first line of input contains an integer T denoting the number of test cases.
- Each test case consists of 1 line with three integers — n1, n2 and m — separated by single spaces.

-----Output-----
For each test case, output a single line containing the minimum sum of the number of stones of two piles.

-----Constraints-----
Subtask 1 : (5 pts)
- 1 ≤ T ≤ 100
- 0 ≤ m ≤ 18
- 0 ≤ n1, n2 ≤ 100
Subtask 2 : (25 pts)
- 1 ≤ T ≤ 1000
- 0 ≤ m ≤ 10000
- 0 ≤ n1, n2 ≤ 10000
Subtask 3 : (70 pts)
- 1 ≤ T ≤ 105
- 0 ≤ m ≤ 109
- 0 ≤ n1, n2 ≤ 1018

-----Example-----
Input:3
1 1 1
1 2 1
4 5 2

Output:0
1
3

-----Explanation-----
Example case 1. : Remove 1 stone from each of the piles. Now 0 stones are remaining, so chef cannot remove any more stones from the piles. Hence, answer is 0+0 = 0
Example case 2. : Again, remove 1 stone from both the piles to get (0,1) stones. Now chef cannot remove any more stones from pile 1, so he stops. Hence, answer is 0+1 = 1.
Example case 3. : First remove 1 stone from both the piles to get (3,4) stones. Now, remove 2 stones from both the piles so that (1,2) stones are remaining. Now chef cannot remove any more stones owing to the condition that he cannot remove the same number of stones twice. So, the answer is 1+2 = 3.

Difficulty: interview

Starter code:

Solutions:
import sys

n = int(sys.stdin.readline())

for _ in range(n):
 p1, p2, m = list(map(int, sys.stdin.readline().split()))

 l = min(p1, p2)

 #while(m > 0 and l > 0):
 #    k = min(l, m)
 #    l -= k
 #    m -= 1

 q = min(p1, p2)
 d = min((m * (m + 1)) / 2, q)

 print(p1 - d + p2 - d)

import sys

n = int(sys.stdin.readline())

for _ in range(n):
 p1, p2, m = list(map(int, sys.stdin.readline().split()))

 l = min(p1, p2)

 while(m > 0 and l > 0):
  k = min(l, m)
  l -= k
  m -= 1

 q = min(p1, p2)
 print(p1 - q + l + p2 - q + l)



n = int(input())

for _ in range(n):
 p1, p2, m = list(map(int, input().split()))

 l = min(p1, p2)

 while(m > 0 and l > 0):
  k = min(l, m)
  l -= k
  m -= 1

 q = min(p1, p2)
 print(p1 - q + l + p2 - q + l)


import math
amb=math.factorial(10)
t=eval(input())
asa=pow(10,10)
li=[]
for i in range(t):
 amb2=math.factorial(10)
 a,b,c=list(map(int,input().split()))
 asa2=pow(10,10)
 d=(c*(c+1))/2
 if d<=a and d<=b:
  li.append(a+b-2*d)
 else:
  amb2=math.factorial(10)
  x=abs(a-b)
  li.append(x)
for i in li:
 print(i)

#t=int(raw_input())
import math
t=eval(input())
while t:
 str=input()
 a,b,r=str.split()
 a=int(a)
 b=int(b)
 r=int(r)
 #print(a,b,r)
 #b=input()
 #r=input()
 t=t-1
 m=min(a,b)
 max_can_remove=(r*(r+1))/2
 ans=0
 if max_can_remove > m:
  ans=abs(a-b)
 else:
  ans=a+b-(2*max_can_remove)
 print(ans)

for _ in range(eval(input())):
 a,b,m=list(map(int,input().split()))
 gsum=(m+1)*m/2
 if gsum<min(a,b):
  print(a+b-2*gsum)
 else:
  print(abs(a-b))


t = int(input())
while t:
 n1,n2,m = [int(x) for x in input().split()]
 if n2<n1:
  temp = n1
  n1 = n2
  n2 = temp
 sum_m = m*(m+1)/2
 if sum_m >= n1:
  print(n2-n1)
 else:
  print(n1+n2-2*sum_m)
 t-=1

# CHEFST.py

t = int(input());
for _ in range(t):
 n1,n2,m = list(map(int,input().split()))
 x = m*(m+1)
 x/=2;
 y = min(x,min(n1,n2));
 ans = (n1+n2)-(y+y)
 print(ans);

def moves(n1, n2, m):
 lower = min(n1, n2)
 sum = max(n1, n2) - lower
 coverage = (m * (m + 1)) / 2
 if(coverage < lower):
  sum = sum + (lower - coverage) * 2
 return sum 

T=int(input())
while T > 0:
 T = T - 1
 list_num = [int(x) for x in input().split()]
 #print list_num
 print(moves(list_num[0], list_num[1], list_num[2]))

import sys 
sys.setrecursionlimit(10000)

def find_min(m,W):
 i=1
 while i <= m :
  if i not in W:
   break
  i+=1
 return i
 
def find_max(M,W,m):
 i=min(M,m)
 while i > 0 :
  if i not in W:
   break
  i-=1
 return i
cache = {}
def knap(M,W,m):
 if len(W)==m or M < find_min(m,W) or M==0 :
  return 0
 if (M,tuple(W),m) in cache:
  return cache[(M,tuple(W),m)]
 if m*(m+1)/2<M:
  cache[(M,tuple(W),m)]=m*(m+1)/2
  return cache[(M,tuple(W),m)]
 #if (M,W,m) in cache:
 #    return cache[(M,W,m)] 
 val = find_max(M,W,m)
 W.add(val)
 #if val == M:
 #    return val
 #print val,M
 #cache[(M,W,m)] = 
 cache[(M,tuple(W),m)] = val+knap(M-val,W,m)
 return cache[(M,tuple(W),m)]

 #return cache[(M,W,m)] 
 
tests = int(input())
for i in range(tests):
 n1,n2,m = ([int(x) for x in input().split(" ")])
 W = set()
 M = min(n1,n2)
 print(max(n1,n2)-M + 2*(M-knap(M,W,m))) 

def find_min(m,W):
 i=1
 while i <= m :
  if i not in W:
   break
  i+=1
 return i
 
def find_max(M,W,m):
 i=min(M,m)
 while i > 0 :
  if i not in W:
   break
  i-=1
 return i
cache = {}
def knap(M,W,m):
 if len(W)==m or M < find_min(m,W) or M==0 :
  return 0
 if (M,tuple(W),m) in cache:
  return cache[(M,tuple(W),m)]
 if m*(m+1)/2<M:
  cache[(M,tuple(W),m)]=m*(m+1)/2
  return cache[(M,tuple(W),m)]
 #if (M,W,m) in cache:
 #    return cache[(M,W,m)] 
 val = find_max(M,W,m)
 W.add(val)
 #if val == M:
 #    return val
 #print val,M
 #cache[(M,W,m)] = 
 cache[(M,tuple(W),m)] = val+knap(M-val,W,m)
 return cache[(M,tuple(W),m)]

 #return cache[(M,W,m)] 
 
tests = int(input())
for i in range(tests):
 n1,n2,m = ([int(x) for x in input().split(" ")])
 W = set()
 M = min(n1,n2)
 print(max(n1,n2)-M + 2*(M-knap(M,W,m))) 

def find_min(m,W):
 i=1
 while i <= m :
  if i not in W:
   break
  i+=1
 return i
 
def find_max(M,W,m):
 i=min(M,m)
 while i > 0 :
  if i not in W:
   break
  i-=1
 return i
 
def knap(M,W,m):
 if len(W)==m or M < find_min(m,W) or M==0 :
  return 0
 if m*(m+1)/2<M:
  return m*(m+1)/2
 #if (M,W,m) in cache:
 #    return cache[(M,W,m)] 
 val = find_max(M,W,m)
 W.add(val)
 #if val == M:
 #    return val
 #print val,M
 #cache[(M,W,m)] = 
 return val+knap(M-val,W,m)
 #return cache[(M,W,m)] 
 
tests = int(input())
for i in range(tests):
 n1,n2,m = ([int(x) for x in input().split(" ")])
 W = set()
 M = min(n1,n2)
 print(max(n1,n2)-M + 2*(M-knap(M,W,m)))