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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't=eval(input())\nwhile t>0:\n xx=list(map(int,input().split()))\n n=xx[0]\n m=xx[1]\n z=xx[2]\n l=xx[3]\n r=xx[4]\n b=xx[5]\n total=z+l+r+b\n maxi=n*m\n count=0\n ar = [[0 for y in range(m)] for x in range(n)]\n truth=True\n i=0\n while i<n:\n  j=0\n  while j<m:\n   ar[i][j]=0\n   if j==0:\n    if l!=0:\n     l=l-1\n     ar[i][0]=-1\n     count=count+1\n     if count==total:\n      truth=False\n      break\n    elif b!=0:\n     b=b-1\n     ar[i][0]=2\n     count=count+1\n     if count==total:\n      truth=False\n      break\n    elif r!=0:\n     r=r-1\n     ar[i][0]=1\n     count=count+1\n     if count==total:\n      truth=False\n      break\n    elif z!=0:\n     z=z-1\n     ar[i][0]=0\n     count=count+1\n     if count==total:\n      truth=False\n      break\n   elif j==(m-1):\n    if ar[i][j-1]==-1:\n     if b!=0:\n      b=b-1\n      ar[i][j]=2\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif l!=0:\n      l=l-1\n      ar[i][j]=-1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n    elif ar[i][j-1]==2:\n     if r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n    elif ar[i][j-1]==1:\n     if r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n    elif ar[i][j-1]==0:\n     if b!=0:\n      b=b-1\n      ar[i][j]=2\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif l!=0:\n      l=l-1\n      ar[i][j]=-1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n   else:\n    if ar[i][j-1]==-1:\n     if l!=0:\n      l=l-1\n      ar[i][j]=-1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif b!=0:\n      b=b-1\n      ar[i][j]=2\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n    elif ar[i][j-1]==2:\n     if r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n    elif ar[i][j-1]==1:\n     if r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n    elif ar[i][j-1]==0:\n     if l!=0:\n      l=l-1\n      ar[i][j]=-1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif b!=0:\n      b=b-1\n      ar[i][j]=2\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif r!=0:\n      r=r-1\n      ar[i][j]=1\n      count=count+1\n      if count==total:\n       truth=False\n       break\n     elif z!=0:\n      z=z-1\n      ar[i][j]=0\n      count=count+1\n      if count==total:\n       truth=False\n       break\n   \n   if truth==False:\n    break\n   j=j+1\n  if truth==False:\n   break\n  i=i+1\n print(count)\n t=t-1\n     \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 19415