Probably everyone has experienced an awkward situation due to shared armrests between seats in cinemas. A highly accomplished cinema manager named "Chef" decided to solve this problem.
When a customer wants to buy a ticket, the clerk at the ticket window asks the visitor if they need the armrests, and if so, which of them: left, right, or both. We know that out of the audience expected to show up, L of them only need the left armrest, R of them need just the right one, Z need none and B need both. Your task is to calculate the maximum number of people that can attend the show. In the cinema hall there are N rows with M seats each. There is only one armrest between two adjacent seats. Seats at the beginning and at the end of the row have two armrests
-----Input-----
Input begins with an integer T: the number of test cases.
Each test case consists of a single line with 6 space-separated integers: N, M, Z, L, R, B.
-----Output-----
For each test case, output a line containing the answer for the task.
-----Constraints and Subtasks-----
- 1 ≤ T ≤ 105 
Subtask 1 : 10 points 
- 1 ≤ N, M ≤ 3 
- 0 ≤ Z, L, R, B ≤ 3 
Subtask 2 : 20 points 
- 1 ≤ N, M ≤ 30 
- 0 ≤ Z, L, R ≤ 30 
- 0 ≤ B ≤ 109 
Subtask 3 : 30 points
- 1 ≤ N, M ≤ 106 
- 0 ≤ Z, L, R ≤ 106 
- 0 ≤ B ≤ 1016 
Subtask 4 : 40 points
- 1 ≤ N, M ≤ 108 
- 0 ≤ Z, L, R, B ≤ 1016 
-----Example-----
Input:2
2 2 3 2 1 1
3 3 1 2 0 9
Output:4
8
-----Explanation-----
'L' - needs left
'R - needs right
'Z' - doesn't need any
'B' - needs both
'-' - empty place
Example case 1.
ZZ
ZB
Example case 2.
LLB
BZB
B-B
def func(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 x=min(b,x)
 ans=ans+x
 b=b-x
 x=l%(m-1)
 ans=ans+x
 x=m-x
 x=min((x/2)+(x%2),b)
 ans=ans+x
 b=b-x
 x=n-(l/(m-1))
 x=x-1
 x=min(b,x*((m/2)+(m%2)))
 ans=ans+x
 z=min(z,n*m-ans)
 ans=ans+z
 return ans
def func2(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 n2=n-x
 x=min(b,x)
 ans=ans+x
 b=b-x
 l=l%(m-1)
 x=l/n2
 ans=ans+x*n2
 m=m-x
 l=l%n2
 ans1=ans+func(n2,m,z,l,0,b)
 ans2=0
 ans3=0
 if(l>0):
  ans2=ans+l
  x=min(z,n2-l)
  ans2=ans2+x
  z=z-x
  m=m-1
  ans2=ans2+func(n2,m,z,0,0,b)
  z=z+x
  m=m+1
  ans3=ans+l
  x=min(b,n2-l)
  ans3=ans3+x
  b=b-x
  m=m-2
  ans3=ans3+func(n2,m,z,0,0,b)
 return max(ans1,ans2,ans3)
t=eval(input())
for _ in range(0,t):
 n,m,z,l,r,b=list(map(int,input().split()))
 a=func(n,m,z,l,r,b)
 a=max(a,func2(n,m,z,l,r,b))
 print(a) 
def func(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 x=min(b,x)
 ans=ans+x
 b=b-x
 x=l%(m-1)
 ans=ans+x
 x=m-x
 x=min((x/2)+(x%2),b)
 ans=ans+x
 b=b-x
 x=n-(l/(m-1))
 x=x-1
 x=min(b,x*((m/2)+(m%2)))
 ans=ans+x
 z=min(z,n*m-ans)
 ans=ans+z
 return ans
def func2(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 n2=n-x
 x=min(b,x)
 ans=ans+x
 b=b-x
 l=l%(m-1)
 x=l/n2
 ans=ans+x*n2
 m=m-x
 l=l%n2
 ans1=ans+func(n2,m,z,l,0,b)
 ans2=0
 ans3=0
 if(l>0):
  ans2=ans+l
  x=min(z,n2-l)
  ans2=ans2+x
  z=z-x
  m=m-1
  ans2=ans2+func(n2,m,z,0,0,b)
  z=z+x
  m=m+1
  ans3=ans+l
  x=min(b,n2-l)
  ans3=ans3+x
  b=b-x
  m=m-2
  ans3=ans3+func(n2,m,z,0,0,b)
 return max(ans1,ans2,ans3)
t=eval(input())
for _ in range(0,t):
 n,m,z,l,r,b=list(map(int,input().split()))
 a=func(n,m,z,l,r,b)
 a=max(a,func2(n,m,z,l,r,b))
 print(a) 