There are n games in a football tournament. Three teams are participating in it. Currently k games had already been played. 

You are an avid football fan, but recently you missed the whole k games. Fortunately, you remember a guess of your friend for these k games. Your friend did not tell exact number of wins of each team, instead he thought that absolute difference between number of wins of first and second team will be d_1 and that of between second and third team will be d_2.

You don't want any of team win the tournament, that is each team should have the same number of wins after n games. That's why you want to know: does there exist a valid tournament satisfying the friend's guess such that no team will win this tournament?

Note that outcome of a match can not be a draw, it has to be either win or loss.


-----Input-----

The first line of the input contains a single integer corresponding to number of test cases t (1 ≤ t ≤ 10^5).

Each of the next t lines will contain four space-separated integers n, k, d_1, d_2 (1 ≤ n ≤ 10^12; 0 ≤ k ≤ n; 0 ≤ d_1, d_2 ≤ k) — data for the current test case.


-----Output-----

For each test case, output a single line containing either "yes" if it is possible to have no winner of tournament, or "no" otherwise (without quotes).


-----Examples-----
Input
5
3 0 0 0
3 3 0 0
6 4 1 0
6 3 3 0
3 3 3 2

Output
yes
yes
yes
no
no



-----Note-----

Sample 1. There has not been any match up to now (k = 0, d_1 = 0, d_2 = 0). If there will be three matches (1-2, 2-3, 3-1) and each team wins once, then at the end each team will have 1 win.

Sample 2. You missed all the games (k = 3). As d_1 = 0 and d_2 = 0, and there is a way to play three games with no winner of tournament (described in the previous sample), the answer is "yes".

Sample 3. You missed 4 matches, and d_1 = 1, d_2 = 0. These four matches can be: 1-2 (win 2), 1-3 (win 3), 1-2 (win 1), 1-3 (win 1). Currently the first team has 2 wins, the second team has 1 win, the third team has 1 win. Two remaining matches can be: 1-2 (win 2), 1-3 (win 3). In the end all the teams have equal number of wins (2 wins).

```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 = "def f1(d1, d2, n, k):\n    a1 = 2 * d1 + d2 + k\n    a2 = -d1 + d2 + k\n    a3 = -d1 - (2 * d2) + k\n    if (a1 < 0 or a2 < 0 or a3 < 0 or a1 % 3 or a2 % 3 or a2 % 3):\n        return False\n    else:\n        a1 //= 3\n        a2 //= 3 \n        a3 //= 3\n        a1, a2, a3 = tuple(sorted([a1, a2, a3])[::-1])\n        if (a2 - a3 + 2 * (a1 - a2)) > n - k:\n            return False\n        else:\n            return True\n\ndef f2(d1, d2, n, k):\n    a1 = -2 * d1 + d2 + k\n    a2 = d1 + d2 + k\n    a3 = d1 - (2 * d2) + k\n    if (a1 < 0 or a2 < 0 or a3 < 0 or a1 % 3 or a2 % 3 or a2 % 3):\n        return False\n    else:\n        a1 //= 3\n        a2 //= 3 \n        a3 //= 3\n        a1, a2, a3 = tuple(sorted([a1, a2, a3])[::-1])\n        if (a2 - a3 + 2 * (a1 - a2)) > n - k:\n            return False\n        else:\n            return True\n\ndef f3(d1, d2, n, k):\n    a1 = 2 * d1 - d2 + k\n    a2 = -d1 - d2 + k\n    a3 = -d1 + (2 * d2) + k\n    if (a1 < 0 or a2 < 0 or a3 < 0 or a1 % 3 or a2 % 3 or a2 % 3):\n        return False\n    else:\n        a1 //= 3\n        a2 //= 3 \n        a3 //= 3\n        a1, a2, a3 = tuple(sorted([a1, a2, a3])[::-1])\n        if (a2 - a3 + 2 * (a1 - a2)) > n - k:\n            return False\n        else:\n            return True\n\ndef f4(d1, d2, n, k):\n    a1 = -2 * d1 - d2 + k\n    a2 = d1 - d2 + k\n    a3 = d1 + (2 * d2) + k\n    if (a1 < 0 or a2 < 0 or a3 < 0 or a1 % 3 or a2 % 3 or a2 % 3):\n        return False\n    else:\n        a1 //= 3\n        a2 //= 3 \n        a3 //= 3\n        a1, a2, a3 = tuple(sorted([a1, a2, a3])[::-1])\n        if (a2 - a3 + 2 * (a1 - a2)) > n - k:\n            return False\n        else:\n            return True\n\n\na = []\nz = int(input())\n\nfor i in range(z):\n    n, k, d1, d2 = map(int, input().split())\n    v1 = f1(d1, d2, n, k)\n    v2 = f2(d1, d2, n, k)\n    v3 = f3(d1, d2, n, k)\n    v4 = f4(d1, d2, n, k)\n    \n        \n    if (v1 or v2 or v3 or v4) and n % 3 == 0:\n        a.append('yes')\n    else:\n        a.append('no')\n    \n    \nprint(*a, sep = '\\n')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13823