You are given a table $a$ of size $n \times m$. We will consider the table rows numbered from top to bottom from $1$ to $n$, and the columns numbered from left to right from $1$ to $m$. We will denote a cell that is in the $i$-th row and in the $j$-th column as $(i, j)$. In the cell $(i, j)$ there is written a number $(i - 1) \cdot m + j$, that is $a_{ij} = (i - 1) \cdot m + j$.

A turtle initially stands in the cell $(1, 1)$ and it wants to come to the cell $(n, m)$. From the cell $(i, j)$ it can in one step go to one of the cells $(i + 1, j)$ or $(i, j + 1)$, if it exists. A path is a sequence of cells in which for every two adjacent in the sequence cells the following satisfies: the turtle can reach from the first cell to the second cell in one step. A cost of a path is the sum of numbers that are written in the cells of the path.

For example, with $n = 2$ and $m = 3$ the table will look as shown above. The turtle can take the following path: $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3)$. The cost of such way is equal to $a_{11} + a_{12} + a_{13} + a_{23} = 12$. On the other hand, the paths $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 1)$ and $(1, 1) \rightarrow (1, 3)$ are incorrect, because in the first path the turtle can't make a step $(2, 2) \rightarrow (2, 1)$, and in the second path it can't make a step $(1, 1) \rightarrow (1, 3)$.

You are asked to tell the turtle a minimal possible cost of a path from the cell $(1, 1)$ to the cell $(n, m)$. Please note that the cells $(1, 1)$ and $(n, m)$ are a part of the way.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of test cases follows.

A single line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^4$) — the number of rows and columns of the table $a$ respectively.


-----Output-----

For each test case output a single integer — a minimal possible cost of a path from the cell $(1, 1)$ to the cell $(n, m)$.


-----Examples-----

Input
7
1 1
2 3
3 2
7 1
1 10
5 5
10000 10000
Output
1
12
13
28
55
85
500099995000


-----Note-----

In the first test case the only possible path consists of a single cell $(1, 1)$.

The path with the minimal cost in the second test case is shown in the statement.

In the fourth and the fifth test cases there is only one path from $(1, 1)$ to $(n, m)$. Both paths visit every cell in the table.

Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
ans = []
for i in range(t):
	(n, m) = input().split(' ')
	m = int(m)
	n = int(n)
	a = m * (m - 1) // 2
	b = m * n * (n + 1) // 2
	ans.append(a + b)
for i in ans:
	print(i)


results = []
test = int(input())
k = 0
while k < test:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	p = m - 1
	col = n * (n + 1) / 2 * m
	row = p * (p + 1) / 2
	summ = col + row
	summ = int(summ)
	results.append(summ)
	k = k + 1
z = 0
while z < test:
	print(results[z], '\n')
	z = z + 1


t = int(input())
res = []
for i in range(t):
	(m, n) = map(int, input().split())
	result = (1 + n) / 2 * n + (n + m * n) / 2 * m - n
	res += [int(result)]
for i in res:
	print(i)


def rc(n, m):
	s = m * (m - 1) / 2
	s = s + n * (n + 1) / 2 * m
	return int(s)
import sys
for line in sys.stdin:
	numbers = [int(x) for x in line.strip().split()]
	if len(numbers) == 2:
		n = numbers[0]
		m = numbers[1]
		print(rc(n, m))


for i in [*open(0)][1:]:
	(n, m) = map(int, i.split())
	print(m * (m - 1 + n * n + n) // 2)


l1 = [int(i) for i in input().split()][:1]
a = l1[0]
l3 = []
for alpha in range(a):
	l2 = [int(k) for k in input().split()][:2]
	l3.append(l2)
for v in range(a):
	n = l3[v][0]
	m = l3[v][1]
	t = m * (m + 1) / 2
	u = m * (n * (n + 1)) / 2
	print(int(t + u - m))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	row = m * (m + 1) // 2
	col = m * (n * (n + 1) // 2) - m
	print(row + col)


x = int(input())
for i in range(x):
	total = 0
	A = input().split()
	n = int(A[1])
	m = int(A[0])
	total = n * (n + 1) / 2 + n * (m * (m + 1) / 2) - n
	p = int(total)
	print(p)


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


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1 or m == 1:
		a = max(m, n)
		ans = a * (a + 1) // 2
	else:
		ans = m * (m + 1) // 2
		ans += n * m * (n - 1) // 2
		ans += (n - 1) * m
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = m * (m + 1) >> 1
	res += m * ((n * (n + 1) >> 1) - 1)
	print(res)


T = int(input())
for i in range(T):
	(m, n) = [int(_) for _ in input().split(' ')]
	print((n * (n + 1) + n * m * (m + 1) - 2 * n) // 2)


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


def optimal_path(n, m):

	def cost_fn(i, j):
		return i * m + j + 1
	min_cost = (1 + m) * m // 2 + (n - 1) * m + m * (n * (n - 1) // 2)
	print(min_cost)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	optimal_path(n, m)


t = int(input(''))
for z in range(t):
	(n, m) = map(int, input('').split())
	s1 = 0
	s2 = 0
	if n == m == 1:
		print(1)
	else:
		s1 = m * (m + 1) / 2
		s2 = n / 2 * (2 * m + (n - 1) * m)
		print(int(s1 + s2 - m))


import sys

def solution_2(n, m):
	return int(m * (m + 1) / 2 + m * (n * (n + 1) / 2 - 1))
case_num = int(sys.stdin.readline().strip())
for case_idx in range(case_num):
	input_ = sys.stdin.readline().strip().split()
	(n, m) = (int(input_[0]), int(input_[1]))
	print(solution_2(n, m))


t = int(input())
for i in range(t):
	L = list(map(int, input().split()))
	(a, b) = (L[0], L[1])
	c = b * (b + 1) // 2 + b * a * (a + 1) / 2 - b
	print(int(c))


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	c = 0
	c += n * (n + 1) // 2
	c += m * (2 * n + (m - 1) * n) // 2
	c -= n
	print(c)


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	return m * (m + 1) // 2 + m * n * (n + 1) // 2 - m
for _ in range(int(input())):
	print(solve())


for t in range(int(input())):
	(n, m) = [int(l) for l in input().split()]
	ans = m * (m + 1) // 2 + m * (n * (n + 1) // 2 - 1)
	print(ans)


T = int(input())
for i in range(T):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	cost = 0
	if n == 1:
		cost = m * (m + 1) / 2
	elif m == 1:
		cost = n * (n + 1) / 2
	else:
		cost = m * (m - 1) / 2 + m * (n * (n + 1) / 2)
	cost = int(cost)
	print(cost)


import sys

def inp():
	return int(input())

def main():
	t = inp()
	while t > 0:
		(n, m) = map(int, input().split())
		A = m * (m + 1) / 2
		B = (n + 2) * (n - 1) * m / 2
		kq = A + B
		print(int(kq), '\n')
		t -= 1
main()


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	s = m * (m + 1) // 2
	s1 = n * (n + 1) // 2
	s1 = s1 - 1
	s1 = s1 * m
	s = s + s1
	print(s)


def su(x):
	return x * (x + 1) / 2
n = int(input())
for i in range(n):
	(n, m) = [int(k) for k in input().split()]
	n_sum = su(n)
	m_sum = su(m)
	ans = n_sum * m + m_sum - m
	print(int(ans))


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


def invr():
	return list(map(int, input().split()))
number_of_test_cases = invr()
while number_of_test_cases[0] > 0:
	arr = invr()
	n = arr[0]
	m = arr[1]
	cost = int((m * (m + 1) + (n - 1) * (4 * m + (n - 2) * m)) / 2)
	print(cost)
	number_of_test_cases[0] = number_of_test_cases[0] - 1


t = int(input())
while t:
	x = input().split(' ')
	n = int(x[0])
	m = int(x[1])
	ans = int(m * (m + 1) / 2)
	ans += int(m * n * (n + 1) / 2 - m)
	print(ans)
	t -= 1


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


for j in [*open(0)][1:]:
	(num, m) = map(int, j.split())
	print(m * (m - 1 + num * num + num) // 2)


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


k = int(input())
l = []
for i in range(k):
	c = [int(x) for x in input().split(' ')]
	n = int(c[0])
	m = int(c[1])
	s = int(m / 2 * (m + 1 + n * (n + 1)) - m)
	l = l + [s]
for j in l:
	print(j)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	n = arr[0]
	m = arr[1]
	result = m * (m - 1) // 2 + n * m * (n + 1) // 2
	print(result)


def solve(n, m):
	cost = m * (m + 1) // 2 + m * (n * (n + 1) // 2) - m
	return cost

def main():
	t = int(input())
	cases = []
	for i in range(t):
		s = input()
		(n, m) = (int(s.split()[0]), int(s.split()[1]))
		cases.append([n, m])
	for i in range(t):
		(n, m) = cases[i]
		res = solve(n, m)
		print(res)
	return
main()


t = int(input())
(n, m) = ([], [])
a = 0
while a < t:
	n.append(0)
	m.append(0)
	(n[a], m[a]) = map(int, input().split())
	a += 1
a = 0
while a < t:
	answer = (m[a] * (m[a] + 1) + n[a] * (n[a] + 1) * m[a]) / 2 - m[a]
	print(int(answer))
	a += 1


def solve_case(n, m):
	horizontal_distance = m * (m + 1) / 2
	vertical_distance = n * (n + 1) / 2 * m - m
	print(int(horizontal_distance + vertical_distance))
num_cases = int(input())
cases = [0] * num_cases
for case in range(num_cases):
	cases[case] = input().split()
for case in cases:
	solve_case(int(case[0]), int(case[1]))


a = [0]
for x in range(1, 10001):
	a.append(a[x - 1] + x)
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	tmp = a[m] + m * (a[n] - 1)
	print(tmp)


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


def take_input():
	cases = int(input())
	n = []
	m = []
	for i in range(cases):
		f = input()
		n.append(int(f.split()[0]))
		m.append(int(f.split()[1]))
	return (n, m, cases)

def ans(row, col):
	a1 = int(col * (col + 1) / 2)
	a2 = int(col * (row * (row + 1) / 2 - 1))
	return a1 + a2

def main():
	(n, m, _) = take_input()
	for i in range(_):
		print(ans(n[i], m[i]))
main()


for _ in range(int(input())):
	(p, q) = map(int, input().split())
	r = q * (q + 1) / 2 + p * q * (p - 1) / 2 + (p - 1) * q
	print(int(r))


case = int(input().strip())
for i in range(case):
	table = input().strip().split(' ')
	table = list(map(int, table))
	x = table[1] - 1
	y = table[0]
	out = 1 * x + x * (x - 1) / 2 + (x + 1) * y + (x + 1) * y * (y - 1) / 2
	print(int(out))


t = int(input())
while t:
	(n, m) = map(int, input().split())
	res = (m - 1) / 2 * m + n / 2 * (m + n * m)
	print(int(res))
	t -= 1


for _ in [*open(0)][1:]:
	(n, m) = map(int, _.split())
	print((m * (m - 1 + n * n + n)).__floordiv__(2))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		print(m * (m + 1) // 2)
	elif m == 1:
		print(n * (n + 1) // 2)
	else:
		p = m * (m - 1) // 2
		q = n * (n + 1) // 2
		q *= m
		print(p + q)


t = int(input())
for k in range(t):
	(m, n) = map(int, input().split())
	s1 = n * (n + 1) // 2
	s2 = m * (m + 1) // 2 - 1
	res = s1 + n * s2
	print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cost = m * (m + 1) // 2
	cost += m * (n * (n + 1)) // 2 - m
	print(cost)


for _ in range(int(input())):
	x = input().split()
	n = int(x[0])
	m = int(x[1])
	sum = m * (m - 1) / 2 + m * (n * (n + 1)) / 2
	print(int(sum))


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


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


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


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	(n, m) = M()
	ans = (m - 1) * m // 2
	ans += m * (n * (n + 1)) // 2
	print(ans)


n = int(input())
for _ in range(n):
	(i, j) = list(map(int, input().split()))
	row = (1 + j) * j / 2
	column = (2 * (j * 2) + j * (i - 2)) / 2 * (i - 1)
	total = row + column
	print(int(total))


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	q1 = int(l[0] * (l[0] + 1) / 2) * l[1]
	q2 = int(l[1] * (l[1] + 1) / 2)
	q3 = q1 + q2 - l[1]
	print(q3)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	a = m * (m - 1) // 2
	b = (n + 1) * n // 2 * m
	print(a + b)


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


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(r, c) = map(int, input().split())
	print(c * (c + 1) // 2 + c * (r * (r + 1) // 2) - c)


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