Given two positive integers a and b, we define f(a, b) = \text{lcm}(a, b) - \gcd(a, b), where \text{lcm} denotes the [lowest common multiple] and \gcd denotes the [greatest common divisor].

Chef has a positive integer N. He wonders, what is the maximum value of f(a, b) over all pairs (a, b) such that a and b are positive integers, and a + b = N?

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

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N, as described in the problem statement. 

------ Output Format ------ 

For each test case, output the maximum value of f(a, b) that can be obtained while satisfying the conditions on a and b. 

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
3
4
6

----- Sample Output 1 ------ 
1
2
4

----- explanation 1 ------ 
Test case $1$: There are two possible pairs of $(a, b)$: $(1, 2)$ and $(2, 1)$. For both of these pairs, we have $\text{lcm}(a, b) = 2$ and $\gcd(a, b) = 1$, which gives $f(a, b) = 1$. 

Test case $2$: For $(1, 3)$, we have $\text{lcm}(1, 3) = 3$ and $\gcd(1, 3) = 1$, giving $f(1, 3) = 3 - 1 = 2$. It can be shown that this is the maximum possible value of $f(a, b)$ that can be obtained while satisfying the above conditions. 

Test case $3$: For $(1, 5)$, we have $\text{lcm}(1, 5) = 5$ and $\gcd(1, 5) = 1$, giving $f(1, 5) = 5 - 1 = 4$. It can be shown that this is the maximum possible value of $f(a, b)$ that can be obtained while satisfying the above conditions.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		p = 1
	elif n % 4 == 0:
		p = n // 2 + 1
	elif n % 2 == 0:
		p = n // 2 + 2
	else:
		p = n // 2 + 1
	q = n - p
	print(p * q - 1)


import numpy as np
t = int(input())
while t:
	n = int(input())
	if n // 2 == 1 or n % 2 != 0:
		print(np.lcm(n // 2, n - n // 2) - np.gcd(n // 2, n - n // 2))
	elif n // 2 % 2 == 0:
		print(np.lcm(n // 2 - 1, n // 2 + 1) - np.gcd(n // 2 - 1, n // 2 + 1))
	else:
		print(np.lcm(n // 2 - 2, n // 2 + 2) - np.gcd(n // 2 - 2, n // 2 + 2))
	t -= 1


import math
tests = int(input())
for i in range(tests):
	n = int(input())
	lower = n // 2
	upper = math.ceil(n / 2)
	gcd = math.gcd(upper, lower)
	ans = upper * lower // gcd - gcd
	while lower > 0 and math.gcd(upper, lower) != 1:
		gcd = math.gcd(upper, lower)
		ans = max(ans, upper * lower // gcd - gcd)
		lower -= 1
		upper += 1
	if lower != 0:
		gcd = math.gcd(upper, lower)
		ans = max(ans, upper * lower // gcd - gcd)
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		x = n // 2
	elif n % 4 == 0:
		x = n // 2 - 1
	elif n == 2:
		x = 1
	else:
		x = n // 2 - 2
	y = n - x
	print(x * y - 1)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	if n & 1:
		ans = (n // 2 + 1) * (n // 2) - 1
	else:
		if n == 2:
			print(0)
			continue
		if n // 2 & 1:
			m = n // 2
			ans = (m - 2) * (m + 2) - 1
		else:
			m = n // 2
			ans = (m - 1) * (m + 1) - 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 2:
		print(0)
	elif n % 2 == 0:
		a = n // 2 - 1
		b = a + 2
		if a % 2 != 0 and b % 2 != 0:
			print(a * b - 1)
		else:
			a -= 1
			b += 1
			print(a * b - 1)
	else:
		a = n // 2
		b = a + 1
		print(a * b - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('0')
	elif n % 2 != 0:
		k = n // 2
		p = k + 1
		print(k * p - 1)
	else:
		k = n // 2 - 1
		p = k + 2
		if k % 2 != 0 and p % 2 != 0:
			print(k * p - 1)
		else:
			k = k - 1
			p = p + 1
			print(k * p - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(0)
	elif n % 2 == 1:
		print((n - 1) // 2 * (n + 1) // 2 - 1)
	elif n % 2 == 0:
		if (n // 2 - 1) % 2 == 1:
			print((n // 2 - 1) * (n // 2 + 1) - 1)
		else:
			print((n // 2 - 2) * (n // 2 + 2) - 1)


import math
T = int(input())
for t in range(T):
	n = int(input())
	x = n // 2
	if n % 2 == 1:
		print(x * (x + 1) - 1)
	elif x > 1:
		if x % 2 == 1:
			print((x - 2) * (x + 2) - 1)
		else:
			print((x - 1) * (x + 1) - 1)
	else:
		print(0)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	i = 1
	f = 0
	a = n // 2
	b = (n + 1) // 2
	if n % 2 == 0:
		a = a - 1
		b = b + 1
	if a % 2 == 0 and b % 2 == 0:
		a -= 1
		b += 1
	if a < 0:
		a = b = 1
	f = a * b - 1
	print(f)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(0)
	elif n % 2 == 1:
		print(n // 2 * (n // 2 + 1) - 1)
	else:
		a = n // 2 - 1
		b = n // 2 + 1
		if a % 2 == 1:
			print(a * b - 1)
		else:
			print((a - 1) * (b + 1) - 1)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		(a, b) = ((n + 1) // 2, (n + 1) // 2 - 1)
	elif n == 2:
		(a, b) = (1, 1)
	elif n // 2 % 2 == 0:
		(a, b) = (n // 2 + 1, n // 2 - 1)
	else:
		(a, b) = (n // 2 + 2, n // 2 - 2)
	g = gcd(a, b)
	l = int(a * b / g)
	print(a * b - 1)


t = int(input())
k = []
for x in range(t):
	N = int(input())
	k = [N - 2]
	if N % 2 == 0:
		if N == 2:
			print(k[0])
		elif int(N / 2) % 2 == 0:
			print((int(N / 2) - 1) * (int(N / 2) + 1) - 1)
		else:
			print((int(N / 2) - 2) * (int(N / 2) + 2) - 1)
	else:
		print(int(N / 2) * (int(N / 2) + 1) - 1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	x = n // 2
	if n == 2:
		print(0)
	elif n % 2 == 0:
		if x % 2 == 0:
			print((x - 1) * (x + 1) - 1)
		else:
			print((x - 2) * (x + 2) - 1)
	else:
		print(x * (x + 1) - 1)


t = int(input())
for j in range(t):
	n = int(input())
	if n & 1:
		a = int(n / 2)
		b = int((n + 1) / 2)
		print(a * b - 1)
	elif n == 2:
		print(0)
	elif n == 4:
		print(2)
	elif n == 6:
		print(4)
	else:
		k = int(n / 2)
		if k & 1:
			a = k - 1
			b = k + 1
		else:
			a = k - 2
			b = k + 2
		x2 = 0
		x1 = (a - 1) * (b + 1) - 1
		if a + 1 != b - 1:
			x2 = (a + 1) * (b - 1) - 1
		print(max(x1, x2))


import math
t = int(input())
while t > 0:
	n = int(input())
	if n == 2:
		print(0)
	else:
		if n % 4 == 0:
			k = (n // 2 - 1) * (n // 2 + 1)
			print(k - 1)
		if n % 4 == 2:
			k = (n // 2 - 2) * (n // 2 + 2)
			print(k - 1)
		if n % 2 == 1:
			print(int(math.floor(n / 2) * math.ceil(n / 2) - 1))
	t -= 1


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return abs(a)
t = int(input())
for x in range(t):
	N = int(input())
	k = 0
	for i in reversed(range(1, N // 2 + 1)):
		if gcd(i, N - i) == 1:
			k = i
			break
	print(k * (N - k) - 1)


from math import ceil, floor

def solve(n):
	if n == 2:
		return 0
	if n & 1 == 1:
		return ceil(n / 2) * floor(n / 2) - 1
	if n % 4 == 0:
		return (n // 2 - 1) * (n // 2 + 1) - 1
	return (n // 2 + 2) * (n // 2 - 2) - 1
t = int(input())
for i in range(t):
	n = int(input())
	print(solve(n))


def g(a, b):
	if b == 0:
		return a
	if a < b:
		return g(b, a)
	return g(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	if n % 2 == 0:
		m = n // 2
		if m % 2 != 0:
			a = n // 2 - 2
			b = n // 2 + 2
			gc = g(a, b)
			lc = a * b // gc
			ans = lc - gc + 1
		else:
			a = n // 2 - 1
			b = n // 2 + 1
			gc = g(a, b)
			lc = a * b // gc
			ans = lc - gc + 1
	else:
		ans = n // 2
		ans *= n // 2 + 1
	if n == 2:
		ans = 1
	print(ans - 1)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 2:
		print(0)
		continue
	if n % 2 == 1:
		print(int((n - 1) // 2 * (n + 1) // 2 - 1))
	elif (n / 2 - 1) % 2 == 1:
		print(int((n // 2 - 1) * (n // 2 + 1) - 1))
	else:
		print(int((n // 2 - 2) * (n // 2 + 2) - 1))


def greatestCommonDivisor(x, y):
	if y == 0:
		return x
	return greatestCommonDivisor(y, x % y)

def solutionFunc(x, y):
	gross = greatestCommonDivisor(x, y)
	part = x * y
	return part // gross - gross
result = ''
for _ in range(int(input())):
	number = int(input())
	if number % 2 == 1:
		result += str(solutionFunc((number - 1) // 2, (number + 1) // 2)) + '\n'
	elif number == 2:
		result += '0\n'
	elif (number // 2 - 1) % 2 == 1:
		result += str(solutionFunc(number // 2 - 1, number // 2 + 1)) + '\n'
	else:
		result += str(solutionFunc(number // 2 - 2, number // 2 + 2)) + '\n'
print(result)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def func(a, b):
	g = gcd(a, b)
	p = a * b
	return p // g - g
ans = ''
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		ans += str(func((n - 1) // 2, (n + 1) // 2)) + '\n'
	elif n == 2:
		ans += '0\n'
	elif (n // 2 - 1) % 2 == 1:
		ans += str(func(n // 2 - 1, n // 2 + 1)) + '\n'
	else:
		ans += str(func(n // 2 - 2, n // 2 + 2)) + '\n'
print(ans)


for i in range(int(input())):
	N = int(input())
	if N == 2:
		print(0)
	elif N % 2 != 0:
		print(N // 2 * (N - N // 2) - 1)
	elif N / 2 % 2 == 0:
		print((N // 2 - 1) * (N // 2 + 1) - 1)
	else:
		print((N // 2 - 2) * (N // 2 + 2) - 1)


import math

def is_coprime(a, b):
	if math.gcd(a, b) == 1:
		return True
	else:
		return False

def max_lcm_hcf(no):
	for i in reversed(range(1, no // 2 + 1)):
		a = i
		b = no - i
		(l, h) = (a * b // math.gcd(a, b), math.gcd(a, b))
		if is_coprime(a, b):
			return l - h
for _ in range(int(input())):
	no = int(input())
	print(max_lcm_hcf(no))


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(0)
	else:
		if n % 2 == 1:
			ret = (n + 1) // 2 * ((n - 1) // 2) - 1
		elif n // 2 % 2 == 0:
			ret = (n + 2) // 2 * ((n - 2) // 2) - 1
		else:
			ret = (n + 4) // 2 * ((n - 4) // 2) - 1
		print(ret)


import sys
import math
from itertools import *
from queue import LifoQueue
from bisect import bisect
from collections import deque, Counter, defaultdict
mod = 10 ** 9 + 7

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def rls():
	return list(map(str, input().split()))

def rm():
	return map(int, input().split())

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def freq(a):
	return Counter(a)

def lcm(x, y):
	return x * y // gcd(x, y)

def compare(x, y):
	return (x > y) - (x < y)

def d2b(n):
	s = bin(n).replace('0b', '')
	return (34 - len(s)) * '0' + s

def BS(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 3:
		return n > 1
	if n & 1 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 2, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
for _ in range(ri()):
	n = ri()
	if n == 2:
		print(0)
		continue
	if n % 2 == 1:
		n //= 2
		ans = n * (n + 1) - 1
	else:
		n //= 2
		if (n - 1) % 2 == 1:
			ans = (n - 1) * (n + 1) - 1
		else:
			ans = (n + 2) * (n - 2) - 1
	print(ans)


for i in range(int(input())):
	x = int(input())
	d = x // 2
	if x == 2:
		print(0)
	elif x % 2 == 0:
		if x / 2 % 2 == 0:
			print((d + 1) * (d - 1) - 1)
		else:
			print((d + 2) * (d - 2) - 1)
	else:
		print(d * (d + 1) - 1)


from sys import stdin
from math import gcd
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(0)
		continue
	if n % 2 == 1:
		print(n // 2 * (n - n // 2) - 1)
	elif n // 2 % 2 == 0:
		n = n // 2
		print((n - 1) * (n + 1) - 1)
	else:
		n = n // 2
		print(max((n - 1) * (n + 1) // gcd(n - 1, n + 1) - 1, (n - 2) * (n + 2) - 1))


try:
	for i in range(int(input())):
		n = int(input())
		if n == 2:
			print(0)
		elif n % 2 != 0:
			print(n // 2 * (n // 2 + 1) - 1)
		elif n / 2 % 2 == 0:
			print((n // 2 - 1) * (n // 2 + 1) - 1)
		else:
			print((n // 2 - 2) * (n // 2 + 2) - 1)
except:
	pass


from math import *
import numpy as np

def lcm(x, y):
	l = x * y // gcd(x, y)
	return l

def solve(n):
	if n & 1:
		return n // 2 * (n // 2 + 1) - 1
	ans = 0
	for i in range(n // 2, 0, -1):
		temp = lcm(i, n - i) - gcd(i, n - i)
		ans = max(ans, temp)
		if gcd(i, n - i) == 1:
			break
	return ans
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


T = int(input())
for t in range(T):
	n = int(input())
	if n % 2 == 1:
		print((n - 1) // 2 * ((n + 1) // 2) - 1)
	elif n == 2:
		print(0)
	elif (n // 2 - 1) % 2 == 1:
		print((n // 2 - 1) * (n // 2 + 1) - 1)
	else:
		print((n // 2 - 2) * (n // 2 + 2) - 1)


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(n // 2 * (n // 2 + 1) - 1)
	elif n % 4 == 0:
		k = n // 2 - 1
		k2 = n - k
		print(k * k2 - 1)
	elif n == 2:
		print(0)
	else:
		kk = n // 2 - 2
		kk2 = n - kk
		print(kk2 * kk - 1)


for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(0)
	elif n % 2 != 0:
		print((n - 1) // 2 * ((n + 1) // 2) - 1)
	elif n % 2 == 0 and n // 2 % 2 == 0:
		print((n // 2 - 1) * (n // 2 + 1) - 1)
	elif n % 2 == 0 and n // 2 % 2 != 0:
		print((n // 2 - 2) * (n // 2 + 2) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2:
		val = n // 2
		print(val * (val + 1) - 1)
	elif n == 2:
		print(0)
	else:
		(mid, k) = (n // 2, 0)
		if mid % 2 == 0:
			k = 1
		else:
			k = 2
		print((mid - k) * (mid + k) - 1)


t = int(input())
for T in range(t):
	N = int(input())
	if N % 2 == 1:
		a = (N - 1) // 2
		b = (N + 1) // 2
	elif N == 2:
		a = 1
		b = 1
	elif N % 4 == 0:
		a = N // 2 - 1
		b = N // 2 + 1
	else:
		a = N // 2 - 2
		b = N // 2 + 2
	print(a * b - 1)


ans = []
for _ in range(int(input())):
	N = int(input())
	N2 = N // 2
	if N == 2:
		an = 0
	elif not N % 2:
		if not N2 % 2:
			an = N2 ** 2 - 2
		else:
			an = N2 ** 2 - 5
	else:
		an = (N - N2) * N2 - 1
	ans.append(an)
print(*ans, sep='\n')


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a / gcd(a, b) * b
for _ in range(int(input())):
	n = int(input())
	l = []
	if n == 2:
		print(0)
	elif n % 2 == 1:
		n = n + 1
		n = int(n / 2)
		l.append(n - 1)
		l.append(n)
		print(n * (n - 1) - 1)
	else:
		n1 = int(n / 2)
		if n1 % 2 == 0:
			l.append(n1 - 1)
			l.append(n1 + 1)
			print((n1 - 1) * (n1 + 1) - 1)
		else:
			n1 = int(n / 2)
			l.append(n1 - 2)
			l.append(n1 + 2)
			print((n1 - 2) * (n1 + 2) - 1)


import math
tc = int(input())
while tc:
	n = int(input())
	if n == 2:
		print(0)
	elif n % 2 != 0:
		k = n // 2
		g = math.gcd(k, k + 1)
		l = k * (k + 1) // g
		print(l - g)
	else:
		v1 = n // 2 - 2
		v2 = n // 2 + 2
		g1 = math.gcd(v1, v2)
		l1 = v1 * v2 // g1
		k1 = l1 - g1
		v3 = n // 2 - 1
		v4 = n // 2 + 1
		g2 = math.gcd(v3, v4)
		l2 = v3 * v4 // g2
		k2 = l2 - g2
		print(max(k1, k2))
	tc -= 1


def gcd(m, n):
	if n == 0:
		return m
	else:
		return gcd(n, m % n)
t = int(input())
while t:
	n = int(input())
	if n == 2:
		print(0)
	elif n % 2 == 0:
		if n // 2 % 2 == 0:
			x = gcd(n // 2 - 1, n // 2 + 1)
			l = (n // 2 - 1) * (n // 2 + 1) // x
			print(l - x)
		else:
			x = gcd(n // 2 - 2, n // 2 + 2)
			l = (n // 2 - 2) * (n // 2 + 2) // x
			print(l - x)
	else:
		print(n // 2 * (n // 2 + 1) - 1)
	t -= 1


for t in range(int(input())):
	N = int(input())
	if N % 2 != 0:
		print((N ** 2 - 1) // 4 - 1)
	elif N == 2:
		print(0)
	elif (N // 2 - 1) % 2 != 0:
		print((N // 2 - 1) * (N // 2 + 1) - 1)
	else:
		print((N // 2 - 2) * (N // 2 + 2) - 1)


from math import gcd
for i in range(int(input())):
	N = int(input())
	if N == 2:
		print(0)
	else:
		if N % 2 != 0:
			(a, b) = ((N + 1) // 2, (N - 1) // 2)
		elif (N // 2 - 1) % 2 != 0 and (N // 2 + 1) % 2 != 0:
			(a, b) = (N // 2 - 1, N // 2 + 1)
		else:
			(a, b) = (N // 2 - 2, N // 2 + 2)
		an2 = gcd(a, b)
		an1 = a * b // an2
		print(an1 - an2)


def printArr(a):
	s = ''
	for i in a:
		s += str(i) + ' '
	print(s[0:-1])
import math
t = int(input())
lcm = lambda a, b, x: a * b // x
for _ in range(t):
	n = int(input())
	if n == 2:
		print(0)
		continue
	t = n // 2
	if n & 1 == 0:
		if t & 1 == 1:
			t += 2
		else:
			t += 1
	x = math.gcd(t, n - t)
	print(lcm(t, n - t, x) - x)


try:
	t = 1
	t = int(input())
	while t > 0:
		n = int(input())
		if n == 2:
			print(0)
		elif n % 2 == 1:
			print((n - 1) // 2 * ((n + 1) // 2) - 1)
		elif n % 2 == 0:
			if (n // 2 - 1) % 2 == 1:
				print((n // 2 - 1) * (n // 2 + 1) - 1)
			else:
				print((n // 2 - 2) * (n // 2 + 2) - 1)
except:
	pass


t = int(input())

def solve(x):
	if x == 2:
		return 0
	t = x // 2
	if x & 1 == 1:
		return t * (t + 1) - 1
	elif t % 2 == 0:
		return (t - 1) * (t + 1) - 1
	else:
		return (t - 2) * (t + 2) - 1
for _ in range(t):
	n = int(input())
	print(solve(n))


import math
t = int(input())
for k in range(t):
	n = int(input())
	if n == 2:
		print(0)
		continue
	if n % 2 == 0:
		c = int(n / 2)
		if c % 2 == 0:
			res = (c - 1) * (n - c + 1) - 1
			print(int(res))
		else:
			res = (c - 2) * (n - c + 2) - 1
			print(int(res))
	else:
		res = n // 2 * (n - n // 2) - 1
		print(int(res))


def gcd(a, b):
	while a != b:
		if a > b:
			a = a - b
		else:
			b = b - a
	return a
for i in range(int(input())):
	n = int(input())
	ans = 0
	x = 0
	if n == 2:
		ans = 0
	elif n == 4:
		ans = 2
	elif n % 2 == 0:
		(x, y) = (n // 2 - 1, n // 2 + 1)
		(c, d) = (n // 2 - 2, n // 2 + 2)
		if x % 2 != 0 and y % 2 != 0:
			ans = x * y - 1
		elif c % 2 != 0 and d % 2 != 0:
			ans = c * d - 1
		elif x % 2 != 0 or y % 2 != 0:
			a1 = gcd(x, y)
			if a1 == 1:
				ans = y * x - 1
		elif c % 2 != 0 or d % 2 != 0:
			a2 = gcd(c, d)
			if a2 == 1:
				ans = c * d - 1
	else:
		ans = (n // 2 + 1) * (n // 2) - 1
	print(ans)