Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Xenny reverse-engineered all the binaries released by the International Security Agency (ISA)
during summer vacation just to pass time. As a reward, the ISA gave him infinite ByteCoins.

Out of sheer boredom and a sense of purposelessness in life, Xenny decided to arrange the Coins on a 2-Dimensional Euclidean Plane.
The boredom was so strong that he arranged these coins in a specific pattern, as opposed to the usual, monotonous way of storing coins in a Piggy Bank.

On each integer co-ordinate (x, y) where x ≥ 0 and y ≥ 0, a single coin was placed. And each coin was assigned a rank. The following pattern was followed in the arrangement:

Let's denote the co-ordinates of the k^{th} coin by (x_{k}, y_{k}) and its rank by R_{k}.

For any 2 coins i, j:

if (x_{i} + y_{i}) < (x_{j} + y_{j}) or ( (x_{i} + y_{i}) == (x_{j} + y_{j}) and x_{i} < x_{j})

then R_{i} < R_{j}. We sort all the coins by this comparison.

The index of the coin (C) in this sorted list of coins (1-indexed) is its rank.

Each query is as follows: Given (U, V). Among the coins that are lying on or inside the rectangle with
its diagonal end-points being (0, 0) and (U, V),
which is the coin that has the maximum rank?

------ Input ------ 

The first line contains an integer, T - the number of testcases.

Each testcase contains 2 space-separated integers: U, V.

------ Output ------ 

For each testcase, print the rank of the maximum ranked coin, on a new line.

------ Constraints ------ 

Subtask 1: (40 points)
$1 ≤ T ≤ 100$
$1 ≤ U, V ≤ 100$
  
Subtask 2: (60 points)
$1 ≤ T ≤ 100$
$1 ≤ U, V ≤ 10^{9}$
  
----- Sample Input 1 ------ 
1
1 2
----- Sample Output 1 ------ 
8

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	(u, v) = map(int, input().split())
	n = u + v - 1
	before = n * (n + 1) // 2 + n + 1
	n_line = u + 1
	print(before + n_line)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	n = a + b
	s = n * (n + 1) // 2 + 1 + a
	print(s)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	n = x + y
	m = n * (n + 1) // 2 + 1 + x
	print(int(m))


T = int(input())
for _ in range(T):
	(U, V) = map(int, input().split())
	n = U + V
	print(n * (n + 1) // 2 + 1 + U)


for t in range(int(input())):
	(x, y) = map(int, input().split())
	d = x + y
	s = d * (d + 1) // 2
	print(x + 1 + s)


T = int(input())
for _ in range(0, T):
	(u, v) = map(int, input().split())
	s = u + v
	print(s * (s + 1) // 2 + u + 1)


n = int(input())
for i in range(n):
	(U, V) = map(int, input().split(' '))
	t = U + V
	print(t * (t + 1) // 2 + U + 1)


def coin_rankings(coordinates):
	summ = sum(coordinates)
	return summ * (summ + 1) // 2 + (coordinates[0] + 1)
for _ in range(int(input())):
	print(coin_rankings(list(map(int, input().split()))))


for _ in range(int(input())):
	(u, v) = map(int, input().split())
	val = u + v + 1
	mx = val * (val + 1) // 2
	print(mx - v)


t = input()
for c in range(0, int(t)):
	(u, v) = map(int, input().split())
	n = u + v - 1
	before = n * (n + 1) // 2 + n + 1
	n_line = u + 1
	print(before + n_line)


tests = int(input())
for i in range(tests):
	(u, v) = map(int, input().split())
	n = u + v
	total = n * (n + 1) // 2 + n + 1
	print(total - v)


tests = int(input())
for i in range(tests):
	(u, v) = map(int, input().split())
	n = u + v - 1
	before = n * (n + 1) // 2 + n + 1
	n_line = u + 1
	print(before + n_line)


for _ in range(int(input())):
	(u, v) = map(int, input().split())
	rank = (u + v) * (u + v + 1) // 2 + u + 1
	print(rank)


T = int(input())
for t in range(T):
	(x, y) = map(int, input().split())
	z = x + y
	print(z * (z + 1) // 2 + x + 1)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	n = x + y
	k = n * (n + 1) // 2 + 1 + x
	print(k)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	print((a + b) * (a + b + 1) // 2 + 1 + a)


t = int(input())
for _ in range(t):
	(u, v) = map(int, input().split())
	sm = u + v
	ans = sm * (sm + 1) // 2 + u + 1
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	sm = x + y
	ans = sm * (sm + 1) // 2 + x + 1
	print(ans)


t = int(input())
for i in range(t):
	(u, v) = map(int, input().split())
	x = u + v
	print(x * (x + 1) // 2 + u + 1)


import sys
import math

def main(U, V):
	n = U + V
	return n * (n + 1) // 2 + U + 1
t = int(input())
for i in range(t):
	(U, V) = list(map(int, input().split()))
	print(main(U, V))


def calc_rank(u, v):
	n = u + v
	sn = n * (n + 1) // 2
	return sn + u + 1
case_count = int(input())
while case_count:
	case_count -= 1
	(u, v) = list(map(int, input().strip().split(' ')))
	print(calc_rank(u, v))


for _ in range(int(input())):
	(u, v) = map(int, input().split(' '))
	s = u + v
	k = s * (s + 1) // 2 + u + 1
	print(k)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
sys.setrecursionlimit(int(pow(10, 6)))
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
t = int(input())
for _ in range(t):
	(u, v) = l()
	x = u + v
	x = x * (x + 1) // 2 + 1
	print(x + u)


t = int(input())
for _ in range(t):
	(u, v) = map(int, input().split())
	x = u + v
	m = x * (x + 1) // 2
	print(u + 1 + m)


for _ in range(int(input())):
	(x, y) = [int(i) for i in input().split()]
	n = x + y
	total = x + 1 + n * (n + 1) // 2
	print(total)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	result = (x + y) * (x + y + 1) // 2 + x + 1
	print(result)


t = int(input())
while t:
	t -= 1
	(u, v) = map(int, input().split())
	ans = 1 + u + (u + v) * (u + v + 1) // 2
	print(ans)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	t = x + y
	print(t * (t + 1) // 2 + t - y + 1)


points = []
for i in range(0, 41):
	for j in range(0, 41):
		points.append([i, j])
points.sort(key=lambda x: [x[0] + x[1], x[0], x[1]])
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = a + b
	z = s
	peeche = z * (z + 1) // 2
	print(peeche + a + 1)


t = int(input())
while t:
	c = [int(x) for x in input().split()]
	n = sum(c)
	print(n * (n + 1) // 2 + c[0] + 1)
	t -= 1


def solve(u, v):
	return (u + v) * (u + v + 1) // 2 + u + 1
for _ in range(int(input())):
	(u, v) = list(map(int, input().split()))
	print(solve(u, v))


for x in range(int(input())):
	(u, v) = [int(a) for a in input().split()]
	ans = u + 1 + (u + v) * (u + v + 1) // 2
	print(int(ans))


t = int(input())
for kk in range(t):
	(x, y) = list(map(int, input().split(' ')))
	ans = (x + y + 1) ** 2 - (x + y) * (x + y + 1) // 2 - y
	print(ans)


t = int(input())
while t > 0:
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	print((x + y) * (x + y + 1) // 2 + x + 1)
	t -= 1


def triangularNumber(n):
	return n * (n + 1) // 2
T = int(input())
for _ in range(T):
	(X, Y) = [int(x) for x in input().split()]
	print(triangularNumber(X + Y) + X + 1)


t = int(input())
while t > 0:
	(u, v) = map(int, input().split(' '))
	s = 1 + u + (u + v) * (u + v + 1) // 2
	print(int(s))
	t -= 1


def main():
	t = int(input())
	while t > 0:
		(x, y) = map(int, input().split(' '))
		rank = (x + y) * (x + y + 1) // 2
		rank += x + 1
		print(int(rank))
		t -= 1
main()


inp = int(input())
for i in range(inp):
	(u, v) = [int(s) for s in input().split()]
	n = u + v
	a = n * (n + 1) // 2
	a += n - v + 1
	print(a)


for test in range(int(input())):
	(a, b) = map(int, input().split())
	z = a + b
	print(z * (z - 1) // 2 + 1 + a + z)


for z in range(int(input())):
	(u, v) = map(int, input().split(' '))
	print((u + v) * (u + v + 1) // 2 + u + 1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	n = x + y + 1
	a = n * (n + 1) // 2
	print(a - y)


import sys
t = int(input())
while t:
	(x, y) = map(int, sys.stdin.readline().split())
	k = x + y
	sumtotal = 0
	p = int((x + y) * (x + y + 1) // 2)
	print(p + x + 1)
	t -= 1


t = int(input())
for c in range(0, t):
	ini = input()
	(u, v) = ini.split()
	u = int(u)
	v = int(v)
	sum = u + v + 1
	res = sum * (sum + 1)
	res = res // 2
	print(res - v)


T = int(input())
while T > 0:
	(U, V) = input().split(' ')
	u = int(U)
	v = int(V)
	t = u + v + 1
	h = t * (t - 1) // 2 + 1
	temp = h + u
	print(temp)
	T = T - 1


def S(n):
	return n * (n + 1) // 2
for t in range(int(input())):
	(x, y) = map(int, input().split())
	print(S(x + y + 1) - y)


T = int(input())
while T > 0:
	(U, V) = [int(x) for x in input().split(' ')]
	print((U + V) * (U + V + 1) // 2 + U + 1)
	T -= 1


T = int(input())
for a0 in range(T):
	(u, v) = input().strip().split()
	(u, v) = [int(u), int(v)]
	n = u + v
	ans = n * (n + 1) // 2
	print(ans + u + 1)


t = int(input())
while t > 0:
	(u, v) = [int(x) for x in input().split(' ')]
	print((u + v) * (u + v + 1) // 2 + u + 1)
	t -= 1


t = int(input())
for a0 in range(t):
	(u, v) = input().strip().split(' ')
	(u, v) = (int(u), int(v))
	print((u + v) * (u + v + 1) // 2 + u + 1)


tc = int(input())
for i in range(tc):
	(u, v) = map(int, input().split())
	result = ((u + v + 1) * (v + u + 1) - (v + u) - 1) // 2 + u + 1
	print(result)


for _ in range(int(input())):
	(u, v) = [int(x) for x in input().split()]
	print((u + v) * (u + v + 1) // 2 + u + 1)


import decimal
t = int(input())
for z in range(t):
	l = input().split()
	(x, y) = (int(l[0]), int(l[1]))
	y = decimal.Decimal(x + y)
	print(decimal.Decimal(x + 1 + y * (y + 1) / 2))


n = int(input())
for i in range(n):
	s = input().split(' ')
	a = int(s[0])
	b = int(s[1])
	x = a + b
	ans = x * (x + 1) // 2
	ans = ans + x + 1 - b
	print(ans)


import bisect

def main(args):
	t = int(input())
	while t > 0:
		(u, v) = map(int, input().split())
		print(rank(u + v) + u)
		t -= 1

def rank(x):
	return 1 + x * (x + 1) // 2
import sys
sys.exit(main(sys.argv))


import math
t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	c = y + x
	count = c * (c + 1) // 2 + 1
	print(int(count + x))
	t = t - 1


def multiply(aaa, bbb):
	aaa.reverse()
	bbb.reverse()
	ccc = [0 for k in range(0, len(aaa) + len(bbb))]
	for i in range(0, len(aaa)):
		for j in range(0, len(bbb)):
			ccc[i + j] += aaa[i] * bbb[j]
	for m in range(0, len(ccc)):
		if ccc[m] > 9:
			ccc[m + 1] += int(ccc[m] / 10)
			ccc[m] = ccc[m] % 10
	ccc.reverse()
	return ccc

def add(aaa, bbb):
	aaa.reverse()
	bbb.reverse()
	(a, b) = (len(aaa), len(bbb))
	c = max(len(aaa), len(bbb)) + 1
	ccc = [0 for k in range(0, c)]
	carry = 0
	for i in range(c):
		if i >= a:
			first = 0
		else:
			first = aaa[i]
		if i >= b:
			second = 0
		else:
			second = bbb[i]
		ccc[i] = first + second + carry
		carry = 0
		if ccc[i] > 9:
			carry = 1
			ccc[i] = ccc[i] - 10
	ccc.reverse()
	return ccc

def int2nums(n):
	return list(map(int, list(str(n))))
t = int(input())
res = []
for i in range(t):
	(u, v) = list(map(int, input().split()))
	if (u + v) % 2 == 0:
		multi = multiply(int2nums(int((u + v) / 2)), int2nums(u + v + 1))
	else:
		multi = multiply(int2nums(u + v), int2nums(int((u + v + 1) / 2)))
	addi = add(multi, int2nums(u + 1))
	res.append(addi)
for i in range(t):
	start = False
	for j in range(len(res[i])):
		if res[i][j] != 0:
			start = True
		if start:
			print(res[i][j], end='')
	print('')


t = int(input())
ry = 1
for j in range(0, t):
	(u, v) = map(int, input().split())
	s = u + v
	ry = s * (s + 1) // 2 + 1
	if u == 0 and v == s:
		print(ry)
		ry = 1
	elif u == s and v == 0:
		print(ry + s)
		ry = 1
	else:
		print(ry + (s - v))
		ry = 1


testt = int(input())
for t in range(testt):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	xx = x
	yy = y
	skip = 0
	p = 0
	q = 0
	maxx = (x + 1) * (y + 1)
	p = xx * (xx + 1) // 2
	yy -= 1
	q = yy * (yy + 1) // 2
	maxx += p + q
	print(maxx)


T = int(input())
for case in range(T):
	(x, y) = map(int, input().split())
	ans = (x + y + 1) * (x + y) // 2 + x + 1
	print(ans)


n = int(input())
for i in range(n):
	(x, y) = list(map(int, input().strip().split(' ')))
	print((x + y) * (x + y + 1) // 2 + x + 1)


T = int(input())
for I in range(T):
	(U, V) = input().split(' ')
	(U, V) = (int(U), int(V))
	Rank = (U + V) * (U + V + 1) // 2
	print(Rank + U + 1)


t = int(input())
for t1 in range(0, t):
	(u, v) = map(int, input().split())
	print((u + v) * (u + v + 1) // 2 + u + 1)