akhauriyash/Code-Regression huggingface dataset:
Chefu is Chef's little brother, he is 12 years old and he is new to competitive programming.
Chefu is practicing very hard to become a very skilled competitive programmer and win gold medal in IOI.
Now Chefu is participating in a contest and the problem that he is trying to solve states:
Given an array A of N integers, find any i, j such that i <  j 
and Ai + Aj is maximum possible 
unfortunately, there's no much time left before the end of the contest, so Chefu doesn't have time to think of correct solution, so instead, he wrote a solution that selects a random pair (i,  j) (i <  j) and output Ai + Aj. each pair is equiprobable to be selected.
Now Chefu wants your help to calculate the probability that his solution will pass a particular input.

-----Input-----
First line contains an integer T denoting the number of test-cases.
First line of each test-case contains a single integer N
Second line of each test-case contains N space-separated integers A1 A2 ... AN

-----Output-----
For each test-case output a single line containing a single number denoting the probability that Chefu's solution to output a correct answer. your answer will be accepted if the absolute difference between it and correct answer is less than 1e-6

-----Constraints-----
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 100
- 1 ≤ Ai ≤ 1,000

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

Output:
1.00000000
0.20000000
0.33333333

```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 = int(input())\n a = sorted(list(map(int, input().split())), reverse=True)\n i = 1\n while i<n-1 and a[i]==a[i+1]:\n  i+=1\n  \n if a[0] == a[1]:\n  print(i*(i+1)/(n*(n-1)))\n else:\n  print(2*i/(n*(n-1)))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13241
There's an array A consisting of N non-zero integers A1..N. A subarray of A is called alternating if any two adjacent elements in it have different signs (i.e. one of them should be negative and the other should be positive).

For each x from 1 to N, compute the length of the longest alternating subarray that starts at x - that is, a subarray Ax..y for the maximum possible y ≥ x. The length of such a subarray is y-x+1.

-----Input-----
- The first line of the input contains an integer T - the number of test cases.
- The first line of each test case contains N.
- The following line contains N space-separated integers A1..N.

-----Output-----
For each test case, output one line with N space-separated integers - the lengths of the longest alternating subarray starting at x, for each x from 1 to N.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- -109 ≤ Ai ≤ 109

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

Output:
1 1 1 1
4 3 2 1
1 1 3 2 1 1

-----Explanation-----
Example case 1. No two elements have different signs, so any alternating subarray may only consist of a single number.
Example case 2. Every subarray is alternating.
Example case 3. The only alternating subarray of length 3 is A3..5.

```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 = "test=int(input())\nfor i in range(test):\n n=int(input())\n a=list(map(int,input().split()))\n b=[0]*(n+2)\n b[n-1]=1\n for i in range(n-2,-1,-1):\n  if(a[i]*a[i+1]<0):\n   b[i]=b[i+1]+1\n  else:\n   b[i]=1\n for i in range(n):\n  print(b[i], end=' ')\n print() "
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13189
Write a function which converts the input string to uppercase.

~~~if:bf
For BF all inputs end with \0, all inputs are lowercases and there is no space between. 
~~~

```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 make_upper_case(st):\n    out = ""\n    for s in st:\n        o = ord(s)\n        if 97 <= o <= 122:\n            o -= 32;\n        out += chr(o)\n    return out'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'make_upper_case'
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: 5442
In this kata you will create a function that takes in a list and returns a list with the reverse order.

### Examples

```python
reverse_list([1,2,3,4]) == [4,3,2,1]
reverse_list([3,1,5,4]) == [4,5,1,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

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 reverse_list(l):\n  rev = []\n  up = len(l) - 1\n\n  for i in range(up, -1, -1):\n    rev.append(l[i])\n\n  return rev'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'reverse_list'
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: 5488
Chef was bored staying at home in the lockdown. He wanted to go out for a change. Chef and Chefu are fond of eating Cakes,so they decided to go the Cake shop where cakes of all possible price are available .
They decided to purchase cakes of equal price and each of them will pay for their cakes. Chef only has coins of denomination $N$ whereas Chefu has that of denomination $M$.
So they want your help to find out the minimum amount to be spent in order to purchase the cakes.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, two integers $N, M$. 

-----Output:-----
For each testcase, output in a single line answer the minimum amount to be spent in order to purchase the cake.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N,M \leq 10^7$

-----Sample Input:-----
1
2 3

-----Sample Output:-----
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 = '# cook your dish here\nt = int(input())\n\ndef gcd(a,b): \n    if a == 0: \n        return b \n    return gcd(b % a, a) \n  \n\ndef lcm(a,b): \n    return (a*b) // gcd(a,b) \n\nfor i in range(t):\n    n,m = map(int, input().split())\n    print(lcm(n,m))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12933
One day, Chef found a cube which has each of its sides painted in some color out of black, blue, red, green, yellow and orange.
Now he asks you to check if he can choose three sides such that they are pairwise adjacent and painted in the same color.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases.
- A single line of each test case contains six words denoting the colors of painted sides in the order: front, back, left, right, top and bottom, respectively.

-----Output-----
For each test case, output a single line containing the word "YES" or "NO" (without quotes) corresponding to the answer of the problem.

-----Constraints-----
- 1 ≤ T ≤  50000 
- Each color will be from the list {"black", "blue", "red", "green", "yellow", "orange"}

-----Subtasks-----
Subtask 1: (25 points)
- 1 ≤ T ≤  12000 
- For each test case there will be at most three different colors

Subtask 2: (75 points)
- Original constraints

-----Example-----
Input:
2
blue yellow green orange black green
green yellow green orange black green

Output:
NO
YES

-----Explanation-----

Example case 1.
There are no three sides with the same color.

Example case 2.
In this test case, the front, bottom and left sides are green (see picture).

```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 t in range(int(input())):\n s = input().split()\n d, loc, p = {}, [], 0\n for x in range(6):\n  if s[x] in d: d[s[x]].append(x)\n  else: d[s[x]] = [x]\n for i in d:\n  if len(d[i]) >= 3:\n   loc = d[i]\n   break\n for l in range(0, 5, 2):\n  if l in loc or (l + 1) in loc: p += 1\n if p == 3: print('YES')\n else: print('NO')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13189
The auditorium of Stanford University is made up of L*R matrix (assume each coordinate has a chair). On the occasion of an event Chef was called as a chief guest. The auditorium was filled with males (M) and females (F), occupying one chair each. Our Chef is very curious guy, so he asks the gatekeeper some queries. The queries were as follows: Is there any K*K sub-matrix in the auditorium which contains all Males or Females.

-----Input-----
- The first line contains three space-separated integers L, R  and Q describing the dimension of the auditorium and the number of questions Chef will ask.
- Each of next L lines contains R characters (M or F).
- Next Q lines contains K and a character (M or F).

-----Output-----
- For each query output "yes" (without quotes) if there exist any K*K sub-matrix in the auditorium which contains all Males (if he asks about Male) or Females (if he asks about Female), otherwise output "no" (without quotes).

-----Constraints and Subtasks-----
- 1 <= L, R, K <= 1000
- 1 <= Q <= 1e6
Subtask 1: 30 points
- 1 <= L, R, Q <= 200
Subtask 2: 70 points
- Original Contraints

-----Example-----
Input:
4 3 3
MMF
MMM
FFM
FFM
2 F
3 M
1 M

Output:
yes
no
yes

```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 chk():\n for r in range(i+1, i+k):\n  if m[r][ix:ix+k] != ss:\n   return False\n return True \nl, r, q = list(map(int, input().split()))\nm = [input().replace(" ", "") for _ in range(l)]\nfor _ in range(q):\n k, s = input().split()\n k = int(k)\n ss = k * s\n ans = "no"\n for i in range(l-k+1):\n  st = 0\n  while ss in m[i][st:]:\n   ix = m[i].index(ss, st)\n   if chk():\n    ans = "yes"\n    break\n   st = ix + 1\n  if ans == "yes":break \n print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13405
Chef Vivek is good in mathematics and likes solving problems on prime numbers. One day his friend Jatin told him about Victory numbers. Victory number can be defined as a number formed after summing up all the prime numbers till given number n. Now, chef Vivek who is very fond of solving questions on prime numbers got busy in some other tasks. Your task is to help him finding victory number.

-----Input:-----
- First line will contain $T$, number of test cases. Then the test cases follow. 
- Each test case contains of a single line of input $N$ till which sum of all prime numbers between 1 to n has to be calculated.

-----Output:-----
For each test case, output in a single line answer to the victory number.

-----Constraints-----
- $1 <= T <= 1000$
- $1 <= N <= 10^6$

-----Sample Input:-----
3
22
13
10

-----Sample Output:-----
77
41
17

```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 primes(n):\n nums = [True for i in range(n+1)] \n lst = []\n p = 2\n while (p * p <= n): \n  if (nums[p] == True): \n   for i in range(p * p, n+1, p): \n    nums[i] = False\n  p += 1\n for p in range(2, n+1): \n  if nums[p]: \n   lst.append(p)\n return lst\nfor _ in range(int(input())):\n n = int(input())\n lst = primes(n)\n print(sum(lst))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13043
The  Chef  has bought $N$ boxes of Tiles. The number of tiles present in  $i^{th}$ box is  $i$  ($i   $ varies from $1$ to $N$) . The Chef  has two houses  with  $N$  rooms  each, whose  floors  is a square with area $(i*i)$ ,i varies from $(1....N)$. He want to distribute equal number of tiles from $i^{th}$ box to any two rooms (each room must belong to one house ) such that all tiles  of $i^ { th}$  box is used and floor of  both rooms of different houses are tiled completely.
Since chef is busy doing some other works so he wants your help to count the total number of rooms of both houses that will be tiled completely.
Note $:$ size of  each tile present in boxes has length and breadth equal to $1$. It is not mandatory to use all the boxes.
A room should be tilled completely from a single box.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains one integer $N$.

-----Output:-----
For each testcase print  the total number of rooms of both houses that will be tiled completely.

-----Constraints-----
- $1 \leq T \leq 5000$
- $1 \leq N \leq 10^{12}$

-----Sample Input:-----
1
16

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

-----EXPLANATION:-----
The room $1$ and $2$ of both the houses are completely tiled.

```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\nimport math\n\nt = int(input())\nwhile t:\n    n = int(input())\n    xx = math.sqrt(n / 2);\n    print(int(2 * int(xx)))\n    t-= 1'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12947
Richik$Richik$ has just completed his engineering and has got a job in one of the firms at Sabrina$Sabrina$ which is ranked among the top seven islands in the world in terms of the pay scale. 
Since Richik$Richik$ has to travel a lot to reach the firm, the owner assigns him a number X$X$, and asks him to come to work only on the day which is a multiple of X$X$. Richik joins the firm on 1-st day but starts working from X-th day. Richik$Richik$ is paid exactly the same amount in Dollars as the day number. For example, if Richik$Richik$ has been assigned X=3$X = 3$, then he will be paid 3$3$ dollars and 6$6$ dollars on the 3rd$3rd$ and 6th$6th$ day on which he comes for work. 
On N−th$N-th$ day, the owner calls up Richik$Richik$ and asks him not to come to his firm anymore. Hence Richik$Richik$ demands his salary of all his working days together. Since it will take a lot of time to add, Richik$Richik$ asks help from people around him, let's see if you can help him out. 

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

-----Output:-----
For each testcase, output in a single line which is the salary which Richik$Richik$ demands. 

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 1≤X<=N≤107$1 \leq X<=N \leq 10^7$

-----Sample Input:-----
1
3 10

-----Sample Output:-----
18

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

```

Measured memory_bytes: 13021
Now that Chef has finished baking and frosting his cupcakes, it's time to package them. Chef has N cupcakes, and needs to decide how many cupcakes to place in each package. Each package must contain the same number of cupcakes. Chef will choose an integer A between 1 and N, inclusive, and place exactly A cupcakes into each package.  Chef makes as many packages as possible. Chef then gets to eat the remaining cupcakes. Chef enjoys eating cupcakes very much. Help Chef choose the package size A that will let him eat as many cupcakes as possible.

-----Input-----

Input begins with an integer T, the number of test cases. Each test case consists of a single integer N, the number of cupcakes.

-----Output-----

For each test case, output the package size that will maximize the number of leftover cupcakes. If multiple package sizes will result in the same number of leftover cupcakes, print the largest such size.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 2 ≤ N ≤ 100000000 (108)

-----Sample Input-----
2
2
5

-----Sample Output-----
2
3

-----Explanation-----

In the first test case, there will be no leftover cupcakes regardless of the size Chef chooses, so he chooses the largest possible size.  In the second test case, there will be 2 leftover cupcakes.

```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\nfor t in range(int(input())):\n    n=int(input())\n    print((n//2)+1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12857
Leha like all kinds of strange things. Recently he liked the function F(n, k). Consider all possible k-element subsets of the set [1, 2, ..., n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets.

But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays A and B, each consists of m integers. For all i, j such that 1 ≤ i, j ≤ m the condition A_{i} ≥ B_{j} holds. Help Leha rearrange the numbers in the array A so that the sum $\sum_{i = 1}^{m} F(A_{i}^{\prime}, B_{i})$ is maximally possible, where A' is already rearranged array.


-----Input-----

First line of input data contains single integer m (1 ≤ m ≤ 2·10^5) — length of arrays A and B.

Next line contains m integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^9) — array A.

Next line contains m integers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ 10^9) — array B.


-----Output-----

Output m integers a'_1, a'_2, ..., a'_{m} — array A' which is permutation of the array A.


-----Examples-----
Input
5
7 3 5 3 4
2 1 3 2 3

Output
4 7 3 5 3

Input
7
4 6 5 8 8 2 6
2 1 2 2 1 1 2

Output
2 6 4 5 8 8 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 = 'import math\nfrom collections import deque, defaultdict\nfrom sys import stdin, stdout\ninput = stdin.readline\n# print = stdout.write\nlistin = lambda : list(map(int, input().split()))\nmapin = lambda : map(int, input().split())\nm = int(input())\na = listin()\nb = listin()\nd = defaultdict(list)\nfor i in range(m):\n    d[b[i]].append(i)\nnums = deque(sorted(d.keys()))\na.sort(reverse = True)\na = deque(a)\nans = [0 for i in range(m)]\nwhile nums:\n    while d[nums[0]]:\n        ans[d[nums[0]].pop()] = a.popleft()\n    nums.popleft()\nprint(*ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14297
Chef solved so many hard questions, now he wants to solve some easy problems for refreshment. Chef asks Cheffina for the new question. Cheffina challanges the chef to print the total number of 1's in the binary representation of N(natural number).

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

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

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

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

-----EXPLANATION:-----
For 1) Binary representation of 2 is 10. i.e. only one 1 present in it.
For 2) Binary representation of 5 is 101, i.e. two 1's present in it.

```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=int(input())\n    s=bin(n)\n    s=s[2:]\n    print(s.count('1'))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12925
Mia is working as a waitress at a breakfast diner. She can take up only one shift from 6 shifts a day i.e. from 10 am to 4 pm. She needs to save 300$ after completion of the month. She works only for $D$ days in the month. She estimates that she gets her highest tip in the first shift and the tip starts decreasing by 2% every hour as the day prolongs. She gets a minimum wage of $X$ $ for every shift. And her highest tip in the first shift is $Y$ $. Determine whether Mia will be able to save 300$ from her wages and tips after working $D$ days of the month. If she can, print YES, else print NO.

-----Constraints-----
- 8 <= D <=30
- 7 <= X <=30
- 4 <= Y <= 20

-----Input:-----
- First line has three parameters $D$, $X$ and $Y$ i.e. number of days worked, minimum wage and highest tip.
- Second line contains D integers indicating her shifts every $i$-th day she has worked.

-----Output:-----
- Print YES, if Mia has saved 300$, NO otherwise.

-----Sample Input:-----
9 17 5
1 3 2 4 5 6 1 2 2

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

-----Explanation:-----
No. of days Mia worked (D) is 9, so minimum wage she earns (X) is 17 dollars. Highest tip at first hour (Y) = 5 dollars, 1st day she took 1st shift and 2nd day she took 3rd shift and so on. Upon calculation we will find that Mia was not able to save 300 dollars.

```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 = 'try:\r\n    def total(i,t):\r\n        dec = 0\r\n        t1 = t\r\n        for i in range(i-1):\r\n            dec = (t1*2)/100\r\n            t1 = dec\r\n        earn = t - (i*dec)\r\n        return earn    \r\n    d,w,t=list(map(int,input().split()))\r\n    s=list(map(int,input().split()))\r\n    m=0\r\n    for i in s:\r\n        m=m+w+total(i,t)\r\n    if m>=300:\r\n        print("YES")\r\n    else:\r\n        print("NO")  \r\nexcept:\r\n    pass'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13213
-----
RANJANA QUIZ
-----

Prof. Ranjana decided to conduct a quiz in her class. She divided all the students of her
class into groups of three. Consider that no student was left out after the division. She gave
different sets of questions to every group. A set is said to be unique if there is no other team that
received the same number of maths, science and english questions. In every set, maximum
questions for each group were related to maths, then science, and the least number of
questions were related to English. Total number of questions given to each team can be
different. 

	
	

After the test, the CR of the class asked every team to report the number of questions
they got on each subject. The CR wants to know the number of unique sets of questions that
were given to the teams, the problem is that all the students have just submitted the number of
questions of each subject but in no particular order. Help the CR to find the number of unique
sets

		
		

-----Input Format-----

Line 1 contains the number of teams ‘n’. In the next n lines, each line contains three space separated integers,i.e, the number of questions of each subject(in no particular order).
employee

-----Output-----

Print the number of unique sets

		
		

-----Example Text Case-----
Input:

5
6 5 4
2 3 7
4 6 5
7 2 3
5 3 1
	
Output:
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=int(input())\nl=[]\nfor i in range(n):\n    a,b,c=list(map(int,input().split()))\n    t=[a,b,c]\n    l.append(sorted(t))\n\nl.sort()\nl1=[]\nfor i in l:\n    l1.append(l.count(i))\ncounter=0\nfor i in l1:\n    if i==1:\n        counter+=  1\nprint(counter)\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13173
Santosh has a farm at Byteland. He has a very big family to look after.  His life takes a sudden turn and he runs into a financial crisis. After giving all the money he has in his hand, he decides to sell his plots. The speciality of his land is that it is rectangular in nature. Santosh comes to know that he will get more money if he sells square shaped plots. So keeping this in mind, he decides to divide his land into minimum possible number of square plots, such that each plot has the same area, and  the plots divide the land perfectly. He does this in order to get the maximum profit out of this.   
So your task is to find the minimum number of square plots with the same area, that can be formed out of the rectangular land, such that they divide it perfectly.

-----Input-----
- The first line of the input contains $T$, the number of test cases. Then $T$ lines follow.
- The first and only line of each test case contains two space-separated integers, $N$ and $M$, the length and the breadth of the land, respectively.

-----Output-----
For each test case, print the minimum number of square plots with equal area, such that they divide the farm land perfectly, in a new line.

-----Constraints-----
$1 \le T \le 20$
$1 \le M \le 10000$
$1 \le N \le 10000$ 

-----Sample Input:-----
2
10 15
4 6

-----SampleOutput:-----
6
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 = '# cook your dish here\nimport math\nN=int(input())\nfor i in range(N):\n a,b=list(map(int,input().split()))\n c=a//math.gcd(a,b)*b//math.gcd(a,b)\n print(c)\n \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13017