You are given an integer $k$. Find the largest integer $x$, where $1 \le x < k$, such that $x! + (x - 1)!^\dagger$ is a multiple of $^\ddagger$ $k$, or determine that no such $x$ exists.

$^\dagger$ $y!$ denotes the factorial of $y$, which is defined recursively as $y! = y \cdot (y-1)!$ for $y \geq 1$ with the base case of $0! = 1$. For example, $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120$.

$^\ddagger$ If $a$ and $b$ are integers, then $a$ is a multiple of $b$ if there exists an integer $c$ such that $a = b \cdot c$. For example, $10$ is a multiple of $5$ but $9$ is not a multiple of $6$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer $k$ ($2 \le k \le 10^9$).


-----Output-----

For each test case output a single integer — the largest possible integer $x$ that satisfies the conditions above.

If no such $x$ exists, output $-1$.


-----Examples-----

Input
4
3
6
8
10
Output
2
5
7
9


-----Note-----

In the first test case, $2! + 1! = 2 + 1 = 3$, which is a multiple of $3$.

In the third test case, $7! + 6! = 5040 + 720 = 5760$, which is a multiple of $8$.

Difficulty: EASY
Tags: Number theory

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import math
import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(int(input())):
	n = inp()
	print(n - 1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	k = int(input())
	print(k - 1)


for i in [*open(0)][1:]:
	print(int(i) - 1)


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	k = inp()
	print(k - 1)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

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

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys

def solve():
	input = sys.stdin.readline
	k = int(input())
	print(k - 1)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


import sys
for i in range(int(sys.stdin.readline())):
	print(int(sys.stdin.readline()) - 1)


for x in [*open(0)][1:]:
	print(int(x) - 1)


import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

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

def readStr():
	return input().strip()

def solve():
	k = readInt()
	return k - 1
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	num = inp()
	inp_arr.append(num)

def findResult(n):
	return n - 1
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	k = int(sys.stdin.readline())
	sys.stdout.write(str(k - 1) + '\n')


from math import factorial
import sys
input = sys.stdin.readline
inp = sys.stdin.readline

def input():
	return inp().strip()

def ii():
	return int(input())

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

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

def solve():
	k = ii()
	print(k - 1)

def main():
	for _ in range(ii()):
		solve()
main()


def main():
	tn = int(input())
	out = []
	for i in range(tn):
		n = int(input())
		out.append(n - 1)
	print(*out, sep='\n')
main()


import math
t = int(input())
l = []
l1 = []
for i in range(t):
	k = int(input())
	l.append(k)
for i in l:
	print(i - 1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		print(n - 1)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	print(n - 1)


import sys
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	k = int(input[i + 1].strip('\n'))
	print(k - 1)


import sys

def in_int():
	return int(sys.stdin.readline())

def in_str():
	return sys.stdin.readline().rstrip()

def in_map_int():
	return map(int, sys.stdin.readline().split())

def in_arr_int():
	return list(map(int, sys.stdin.readline().split()))

def in_arr_str():
	return sys.stdin.readline().split()

def is_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return True
	return False

def bin2dec(s):
	n = 0
	for i in range(len(s)):
		n += int(s[len(s) - i - 1]) * 2 ** i
	return n

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a

def dec2bin(n):
	if n == 0:
		return '0'
	ans = ''
	while n > 0:
		ans += str(n % 2)
		n //= 2
	return ans[::-1]

def solve(n):
	return n - 1

def main():
	t = in_int()
	for _ in range(t):
		n = in_int()
		print(solve(n))
main()


t = int(input(''))
A = []
for i in range(t):
	n = int(input(''))
	A.append(n)
for i in range(t):
	print(A[i] - 1)


a = int(input())
t = []
for i in range(a):
	s = int(input())
	t.append(s)

def main(no):
	if no == 1:
		return -1
	else:
		return no - 1
for z in t:
	print(main(z))


import math as m
l = []
for i in range(int(input())):
	k = int(input())
	l.append(k - 1)
for i in l:
	print(i)


cases = int(input())
inp = []
for _ in range(cases):
	inp.append(int(input()))
for inpt in inp:
	print(inpt - 1)


n = int(input())
I = []
for i in range(n):
	I.append(int(input()))

def convex(k):
	if k > 1:
		return k - 1
	else:
		return -1
for e in I:
	print(convex(e))


print('\n'.join([str(int(it[:-1]) - 1) for it in [*open(0)][1:]]))


t = int(input())
a = []
for i in range(t):
	a.append(int(input()))
for i in a:
	print(i - 1)


def factorial(num):
	fact = 1
	for i in range(1, num + 1):
		fact = fact * i
	return fact
n = int(input())
testCases = [None] * n
results = [None] * n
i = 1
x = 0
for j in range(0, n):
	testCases[j] = int(input())
for j in range(0, n):
	results[j] = testCases[j] - 1
for result in results:
	print(result)


for n in [*open(0)][1:]:
	print(int(n) - 1)


t = int(input())
check = [int(input()) for i in range(t)]
for i in check:
	x = i - 1
	print(x)


t = int(input())
result = []
for i in range(t):
	n = int(input())
	if n == 1:
		result.append(1)
	else:
		result.append(n - 1)
for i in result:
	print(i)


out = []
for _ in range(int(input())):
	k = int(input())
	out.append(k - 1)
for i in out:
	print(i)


import sys
import itertools
import bisect
import math
import collections
t = int(sys.stdin.readline())
while t >= 1:
	n = int(sys.stdin.readline())
	sys.stdout.write(str(n - 1))
	sys.stdout.write('\n')
	t -= 1


t = int(input())
res = []
for _ in range(t):
	k = int(input())
	res.append(k - 1)
for i in res:
	print(i)


def solve(n):
	print(n - 1)
no_of_tests = int(input())
problems = []
for _ in range(no_of_tests):
	problems.append(int(input()))
for each in problems:
	solve(each)


a = int(input())
li1 = []
for i in range(a):
	li1.append(int(input()))
for i in li1:
	print(i - 1)


numtestcases = int(input())
output = []
for i in range(numtestcases):
	output.append(int(input()) - 1)
for answer in output:
	print(answer)


import heapq
import sys
import math
import itertools
import os
input = lambda : sys.stdin.readline().strip()

def solve():
	n = int(input())
	print(n - 1)
for i in range(int(input())):
	solve()


a = int(input())
l = []
for i in range(a):
	l.append(int(input()) - 1)
for i in l:
	print(i)


n_sets = int(input())
answer = [int(input()) - 1 for testcase in range(n_sets)]
for x in answer:
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	print(n - 1)


t = int(input())
for _ in range(t):
	k = int(input())
	print(k - 1)


for _ in range(int(input())):
	a = int(input())
	print(a - 1)


t = int(input())
for i in range(t):
	n = int(input())
	print(n - 1)


test = int(input())
for t in range(test):
	n = int(input())
	print(n - 1)


import math

def fact(a):
	return math.factorial(a)
t = int(input())
while t:
	a = int(input())
	print(a - 1)
	t = t - 1


t = int(input())
for i in range(0, t):
	k = int(input())
	print(k - 1)


n = int(input())
for x in range(n):
	k = int(input())
	if k == 1:
		print(-1)
	else:
		print(k - 1)


from math import factorial as f
t = int(input())
for i in range(t):
	k = int(input())
	if k == 1:
		print(-1)
	else:
		print(k - 1)


T = int(input())
for i in range(T):
	k = int(input())
	print(k - 1)


answer = [print(int(input()) - 1) for testcase in range(int(input()))]


tst = int(input())
for i in range(tst):
	num = int(input())
	print(num - 1)


t = int(input())
for _ in range(t):
	k = int(input())
	if k == 0 or k == 1:
		print(-1)
	else:
		n = k - 1
		print(n)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print(n - 1)


t = int(input())
while t > 0:
	t -= 1
	k = int(input())
	print(k - 1)


a = int(input())
for i in range(a):
	print(int(input()) - 1)


tests = int(input())
for _ in range(tests):
	n = int(input())
	print(n - 1)