akhauriyash/Code-Regression huggingface dataset:
We have a sequence A of N non-negative integers.
Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).
Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2000
 - 1 \leq M \leq 10^9
 - 0 \leq A_i \leq 2000

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_N

-----Output-----
Print the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i}, modulo (10^9 + 7).

-----Sample Input-----
3 5
1 2 1

-----Sample Output-----
8

There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:
 - B = \{1, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;
 - B = \{2, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;
 - B = \{1, 3, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;
 - B = \{1, 2, 2\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.
The sum of these is 1 + 2 + 3 + 2 = 8.

```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 = 'mod = 10**9+7\nn, m = map(int, input().split())\ns = sum(map(int, input().split()))\na = n+m\nb = s+n\nnum = 1\nden = 1\nfor i in range(b):\n  num *= a-i\n  num %= mod\n  den *= i+1\n  den %= mod\nans = num * pow(den, mod-2, mod) % mod\nprint(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13085
Hooray! Polycarp turned $n$ years old! The Technocup Team sincerely congratulates Polycarp!

Polycarp celebrated all of his $n$ birthdays: from the $1$-th to the $n$-th. At the moment, he is wondering: how many times he turned beautiful number of years?

According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: $1$, $77$, $777$, $44$ and $999999$. The following numbers are not beautiful: $12$, $11110$, $6969$ and $987654321$.

Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).

Help Polycarpus to find the number of numbers from $1$ to $n$ (inclusive) that are beautiful.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case consists of one line, which contains a positive integer $n$ ($1 \le n \le 10^9$) — how many years Polycarp has turned.


-----Output-----

Print $t$ integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between $1$ and $n$, inclusive.


-----Example-----
Input
6
18
1
9
100500
33
1000000000

Output
10
1
9
45
12
81



-----Note-----

In the first test case of the example beautiful years are $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ and $11$.

```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 = int(input())\nfor i in range(t):\n    k = 0\n    n = input()\n    k += (len(n) - 1) * 9\n    if n[0] * len(n) > n:\n        k += int(n[0]) - 1\n    else:\n        k += int(n[0])\n    print(k)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13011
Mr. Pr and Ms. Ad are at $a$ and $b$ respectively on an infinite number line. Mr. Pr wants to meet Ms. Ad.
Mr. Pr can choose to move  $c$ or $d$ units in 1 second. If Mr. Pr moves $c$ units then Ms. Ad will move $d$ units and vice versa. (Both of them always moved in positive x-direction)
You have to determine if Mr. Pr can meet with Ms. Ad after some integral amount of time, given that Mr. Pr chooses optimally. Note that meeting after a fractional amount of time does not count.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains four space separated integers, $a$, $b$, $c$, and $d$.

-----Output:-----
- For each test case, output a single line containing "YES" if Mr. Pr meets with Ms. Ad, otherwise "NO".

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq a,b,c,d \leq 10^9$

-----Sample Input:-----
2
3 4 1 2
10 20 3 7

-----Sample Output:-----
YES
NO

-----Explanation:-----
In the first test case, Mr. Pr will move 2 units in the first second and Ms. Ad moves 1 unit simultaneously and they meet. 
In the second test case, it is impossible to meet (fractional time is not allowed).

```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 = 'import math\r\nt=int(input())\r\nwhile(t>0):\r\n    a,b,c,d=input().split()\r\n    a=int(a)\r\n    b=int(b)\r\n    c=int(c)\r\n    d=int(d)\r\n    if d==c:\r\n        if a==b:\r\n            print("YES")\r\n        else:\r\n            print("NO")\r\n    else:\r\n        m=((a-b)%(c-d))\r\n        if(m==0):\r\n            print("YES")\r\n        else:\r\n            print("NO")\r\n    t=t-1\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13097
# Grasshopper - Function syntax debugging

A student was working on a function and made some syntax mistakes while coding. Help them find their mistakes and fix them.

```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

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def main (verb, noun):\n    output = verb + noun\n    return output'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'main'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5334
Write a program to obtain a number $N$ and increment its value by 1 if the number is divisible by 4 $otherwise$ decrement its value by 1.

-----Input:-----
- First line will contain a number $N$.

-----Output:-----
Output a single line, the new value of the number.

-----Constraints-----
- $0 \leq N \leq 1000$

-----Sample Input:-----
5

-----Sample Output:-----
4

-----EXPLANATION:-----
Since 5 is not divisible by 4 hence, its value is decreased by 1.

```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 = 'a=int(input())\nif a%4==0:\n    print(a+1)\nelse:\n    print(a-1)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12823
You are given a set of n pens, each of them can be red, blue, green, orange, and violet in color. Count a minimum number of pens that should be taken out from the set so that any two neighboring pens have different colors. Pens are considered to be neighboring if there are no other pens between them.

-----Input:-----
- 
The first line contains t denoting the number of test cases.
- 
The first line of each test case will contain a single integer n.
- 
The second line of each test case will contain a string s.
(s contains only 'R', 'B', 'G', 'O', and 'V' characters denoting red, blue, green, orange, and violet respectively)

-----Output:-----
For each test case, print single line containing one integer - The minimum number of pens that need to be taken out.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq n \leq 1000$

-----Sample Input:-----
2
5
RBBRG
5
RBGOV

-----Sample Output:-----
1
0

-----EXPLANATION:-----
In first test case, two blue pens are neighboring each other, if we take out any one of them then the string will be RBRG in which each pen has different neighbors.
In second test case, no pen needs to be taken out as each pen has different neighbors.

```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 = "# cook your dish here\nt = int(input())\n\nfor _ in range(t):\n    n = int(input())\n    s = str(input())\n    prev = ''\n    count = 0\n    for i in s:\n        if i == prev:\n            count += 1\n        else:\n            prev = i\n    \n    print(count)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12925
Given a number **n**, return the number of positive odd numbers below **n**, EASY!

Expect large Inputs!

```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

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def odd_count(n):\n    print(n)\n    if n % 2:\n        return ((n+1)/2)-1\n    return n/2'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'odd_count'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5593
In a fictitious city of CODASLAM there were many skyscrapers. The mayor of the city decided to make the city beautiful and for this he decided to arrange the skyscrapers in descending order of their height, and the order must be strictly decreasing but he also didn’t want to waste much money so he decided to get the minimum cuts possible. Your job is to output the minimum value of cut that is possible to arrange the skyscrapers in descending order.

-----Input-----

*First line of input is the number of sky-scrappers in the city
*Second line of input is the height of the respective sky-scrappers


-----Output-----

* Your output should be the minimum value of cut required to arrange these sky-scrappers in descending order.

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

Output:
8

By:
Chintan,Asad,Ashayam,Akanksha

```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 = '#!/usr/bin/env python\n\ndef main():\n N = int(input())\n while True:\n  try:\n   X = input()\n  except:\n   break\n  H = list(map(int, X.split()))\n  C = 0\n  while H:\n   e = H.pop(0)\n   H2, C1, C2 = list(H), e, 0\n   for i in range(len(H2)):\n    if H2[i] > e-1:\n     C2 += H2[i]-(e-1)\n     H2[i] = e-1\n   #print C+C2, H2, C+C1, H\n   if C1 <= C2:\n    C += C1\n   else:\n    C += C2\n    H = H2\n  print(C)\n\nmain()\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14287
Andrii is good in Math, but not in Programming. He is asking you to solve following problem: Given an integer number N and two sets of integer A and B. Let set A contain all numbers from 1 to N and set B contain all numbers from N + 1 to 2N. Multiset C contains all sums a + b such that a belongs to A and b belongs to B. Note that multiset may contain several elements with the same values. For example, if N equals to three, then A = {1, 2, 3}, B = {4, 5, 6} and C = {5, 6, 6, 7, 7, 7, 8, 8, 9}. Andrii has M queries about multiset C. Every query is defined by a single integer q. Andrii wants to know the number of times q is contained in C. For example, number 6 is contained two times, 1 is not contained in C at all. 

Please, help Andrii to answer all the queries.

-----Input-----

The first line of the input contains two integers N and M. Each of the next M line contains one integer q, the query asked by Andrii.

-----Output-----
Output the answer for each query in separate lines as in example.

-----Constraints-----
- 1 ≤ N ≤ 109
- 1 ≤ M ≤ 105
- 1 ≤ q ≤ 3N

-----Example-----
Input:
3 5
6
2
9
7
5
Output:
2
0
1
3
1

```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 = "n,m = map(int,input().split())\r\nfor i in range(m):\r\n    q = int(input())\r\n    if q>n+1: print(q-n-1) if q<2*(n+1) else print(3*n-q+1)\r\n    else: print('0')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13003
You are given an array of N integers a1, a2, ..., aN and an integer K. Find the number of such unordered pairs {i, j} that 

- i ≠ j
- |ai + aj - K| is minimal possible

Output  the minimal possible value of |ai + aj - K| (where i ≠ j) and the number of such pairs for the given array and the integer K.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case consists of two space separated integers - N and K respectively.

The second line contains N single space separated integers - a1, a2, ..., aN respectively.

-----Output-----
For each test case, output a single line containing two single space separated integers - the minimal possible value of |ai + aj - K| and the number of unordered pairs {i, j} for which this minimal difference is reached.

-----Constraints-----

- 1 ≤ T ≤ 50
- 1 ≤ ai, K ≤ 109
- N = 2 - 31 point.
- 2 ≤ N ≤ 1000 - 69 points.

-----Example-----
Input:
1   
4 9
4 4 2 6

Output:
1 4

-----Explanation:-----
The minimal possible absolute difference of 1 can be obtained by taking the pairs of a1 and a2, a1 and a4, a2 and a4, a3 and a4.

```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 = 'for _ in range(int(input())):\n n,k=map(int,input().split())\n l=list(map(int,input().split()))\n aux=[]\n for i in range(len(l)):\n  for j in range(i+1,len(l)):\n   aux.append(abs(l[i]+l[j]-k))\n m=min(aux)\n t_1=aux.count(m)\n print(m,t_1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13281
As lockdown is going on so no is allowed to go outside , so Chef has come with an innovative idea for food home delivery using drone.  But there is an issue with it , the drone can move forward or backward a fix number of steps $x$ . 
All the houses and chef restaurant are all in a straight line . Homes which need delivery are located at $H[i]$ and chef is located at $y$ coordinate . 
If Drone is at a location $R$, then it can move to $R-x$ or $R+x$ . 
Help chef find maximum value of $x$ to complete all the deliveries as he is busy managing the orders.

-----Input:-----
- First line will contain $n$ and $R$, number of houses that need delivery and the correct coordinate of chef (Drone).
- Second line contains $n$ integers , the coordinate of all homes that need delivery. 

-----Output:-----
- The maximum value of $x$ , so that drone delivers to all houses.

-----Constraints-----
- $1 \leq n \leq 1000$
- $1 \leq R \leq 10^9$
- $1 \leq hi \leq 10^9$
- $1 \leq x  \leq 10^9$

-----Sample Input:-----
3 1
3 5 11

-----Sample Output:-----
2

-----EXPLANATION:-----
Chef's drone is at 1 initially and he needs to visit 3,5,11 , so optimal solution will be (maximum value of x ) equal to 2.

```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 gcd(a, b):\r\n    while b > 0:\r\n        a, b = b, a % b\r\n    return a\r\n\r\na = [4, 10, 16, 14]\r\nn,r=map(int,input().split())\r\nlst=[r]\r\nlst.extend(list(map(int,input().split())))\r\nnlst=[]\r\nfor i in range(0,n-1):\r\n\tnlst.append(lst[i+1]-lst[i])\r\nresult = nlst[0]\r\nfor i in nlst[1:]:\r\n    result = gcd(result, i)\r\n\r\nprint(result)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13427
Given an integer N, Chef wants to find the smallest positive integer M such that the bitwise XOR of M and M+1 is N. If no such M exists output -1.

-----Input-----
The first line of input contain an integer T denoting the number of test cases. Each of the following T lines contains an integer N for that test case.

-----Output-----
For each test case, output a single line containing the number M or -1 as described above.

-----Constraints-----
- 1 ≤ T ≤ 5000
- 1 ≤ N ≤ 230

-----Example-----
Input:
1
3

Output:
1

-----Explanation-----First Example :  M desired in the problem would be 1. As bitwise XOR of 1 and 2 is equal to 3.

```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 = "# cook your dish here\nT=int(input())\nfor i in range(T):\n N=int(input())\n f=bin(N)[2:]\n if f.count('0')==0:\n  if N==1:\n   print(2)\n  else:\n   print(N>>1)\n else:\n  print(-1)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12995
This is probably the simplest problem ever. You just need to count the number of ordered triples of different numbers (X1, X2, X3), where Xi could be any positive integer from 1 to Ni, inclusive (i = 1, 2, 3).
No, wait. I forgot to mention that numbers N1, N2, N3 could be up to 1018. Well, in any case it is still quite simple :)
By the way, because of this the answer could be quite large. Hence you should output it modulo 109 + 7. That is you need to find the remainder of the division of the number of required triples by 109 + 7.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains three space-separated integers N1, N2, N3.

-----Output-----
For each test case, output a single line containing the number of required triples modulo 109 + 7.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ Ni ≤ 1018

-----Example-----
Input:
5
3 3 3
2 4 2
1 2 3
25 12 2012
1 1 2013

Output:
6
4
1
578880
0

-----Explanation-----
Example case 1. We have the following triples composed of different numbers up to 3:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Example case 2. Here the triples are:
(1, 3, 2)
(1, 4, 2)
(2, 3, 1)
(2, 4, 1)
Example case 3. Here the only triple is (1, 2, 3).
Example case 4. Merry Christmas! 
Example case 5. ... and Happy New Year! By the way here the answer is zero since the only choice for X1 and for is X2 is 1, so any such triple will have equal numbers.

```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 = 'd=1000000007\nfor _ in range(int(input())):\n l=sorted(list(map(int,input().split())))\n ans=(l[0]%d)*((l[1]-1)%d)*((l[2]-2)%d)\n print(ans%d)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13043
Motu and Patlu are racing against each other on a circular track of radius $R$. Initially they are at the same point on the track and will run in same direction .The coach ordered them to run $X$ rounds of the circular field. Patlu wants to know how many times they will meet after the race starts and  before any of them finishes $X$ rounds. But he is busy in warm up so he wants you to calculate this. You are given speed of both Motu and Patlu ($A$ and $B$). 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, four integers $X, R, A, B$. 

-----Output:-----
For each testcase, output in a single line answer the number of times whey will meet before any of them completes $X$ rounds.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq R \leq 10^9$
- $1 \leq X \leq 10^9$
- $1 \leq A \leq 10^9$
- $1 \leq B \leq 10^9$
- Speed of both are different

-----Sample Input:-----
2
3 10 2 5
2 20 5 10

-----Sample Output:-----
1
0

```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 = '# cook your dish here\na=int(input())\nfor i in range(0,a):\n x,r,a,b=map(int,input().split())\n maxx=max(a,b)\n minn=min(a,b)\n ans=x-x*(minn/maxx)\n if(ans-int(ans)==0):\n  ans=ans-1 \n else:\n  ans=int(ans)\n print(int(ans))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13057
Bob has got some injury in his leg and due to this he can take exactly M steps in one move. 
Bob enters a square field of size NxN. The field is only having one gate(for both entrance and exit) at its one of the corners. Bob started walking along the perimeter of square field.(remember Bob can only take exactly M steps in one move and cannot reverse his direction of motion).
Bob wants to know how many minimum number of moves he needs to come out(i.e. he reaches the same gate from where he entered into the field) from the square field. Tell the answer to Bob ASAP.
Luckily, you came to know M=N+1.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases.
-  Each test case contains a single integer N denoting the sides of the square.

-----Output-----
- For each test case, output a single line containing minimum number of moves Bob required to come out from the field.

-----Constraints-----
- 1 ≤ T ≤ 10000
- 1 ≤ N ≤ 1000000000

-----Example-----
Input:
2
1
2

Output:
2
8

-----Explanation-----
Example case 1.Let four corners of square be (0,0), (0,1), (1,1), (1,0). Let gate be at (0,0). Bob takes 2 steps in one move. Let movement of Bob be as follows (0,0) -> (1,1) -> (0,0). Thus minimum moves needed were 2. 
Example case 2.Let four corners of square be (0,0), (0,2), (2,2), (2,0). Let gate be at (0,0). Bob takes 3 steps in one move. Let movement of Bob be as follows (0,0) -> (2,1) -> (0,2) -> (1,0) -> (2,2) -> (0,1) -> (2,0) -> (1,2) -> (0,0). Thus minimum number of moves needed are 8.

```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 = '# your code goes here\ndef gcd(a,b):\n if b==0:\n  return a\n else:\n  return gcd(b,a%b)\n  \nt=int(input().strip())\nwhile t:\n a=int(input().strip())\n b=a*4\n a+=1\n ans=b/gcd(b,a)\n print(ans)\n t-=1'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13115
Give me Biscuit

Sunny wants to make slices of biscuit of size c * d into identical pieces.

but each piece is a square having maximum possible side length with no left over piece of biscuit.

Input Format

The first line contains an integer N.

N lines follow. Each line contains two space separated integers c and d.

which denote length and breadth of the biscuit.

Constraints

1 <= N <= 1000

1 <= c,d <= 1000
Output Format

N lines, each containing an integer that denotes the number of squares of maximum size, when the biscuit is cut as per the given condition.

Sample Input 

2

2 2

6 9

Sample Output 

1

6

Explanation 
	

The 1st testcase has a biscuit whose original dimensions are 2 X 2, the biscuit is uncut and is a square.

Hence the answer is 1.

The 2nd testcase has a biscuit of size 6 X 9 . We can cut it into 54 squares of size 1 X 1 , 6 of size 3 X 3 . For other sizes we will have leftovers.

Hence, the number of squares of maximum size that can be cut is 6.

```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 = "\n\n\n# Python3 code for calculating\n# the number of squares\n\n# Recursive function to\n# return gcd of a and b\ndef __gcd(a, b):\n # Everything divides 0\n if (a == 0 or b == 0):\n  return 0;\n\n  # base case\n if (a == b):\n  return a;\n\n  # a is greater\n if (a > b):\n  return __gcd(a - b, b);\n return __gcd(a, b - a);\n\n\n# Function to find\n# number of squares\ndef NumberOfSquares(x, y):\n # Here in built PHP\n # gcd function is used\n s = __gcd(x, y);\n\n ans = (x * y) / (s * s);\n\n return int(ans);\n\n\n# Driver Code\n\nt = int(input())\nfor i in range(t):\n m,n = list(map(int,input().split(' ')))\n# Call the function\n# NumberOfSquares\n print((NumberOfSquares(m, n)));\n\n# This code is contributed\n# by mit\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13273
Chef has a number N, Cheffina challenges the chef to check the divisibility of all the permutation of N by 5. If any of the permutations is divisible by 5 then print 1 else print 0.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input,$N$. 

-----Output:-----
For each test case, output in a single line answer 1 or 0.

-----Constraints-----
- $1 \leq T \leq 10^6$
- $1 \leq N \leq 10^6$

-----Sample Input:-----
2
19
385

-----Sample Output:-----
0
1

```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=int(input())\r\n\r\nfor _ in range(T):\r\n    \r\n    N=input()\r\n    if '0' in N or'5' in N:\r\n        print(1)\r\n    else:\r\n        print(0)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12855