A. Кратные факториалу
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано натуральное число $$$k$$$. Найдите наибольшее натуральное число $$$x$$$, где $$$1 \le x < k$$$, такое, что $$$x! + (x - 1)!^\dagger$$$ кратно $$$^\ddagger$$$ числу $$$k$$$, или определите, что такого $$$x$$$ не существует.

$$$^\dagger$$$ $$$y!$$$ обозначает факториал числа $$$y$$$: $$$0! = 1$$$, а для $$$y \geq 1$$$ факториал задаётся рекуррентно: $$$y! = y \cdot (y-1)!$$$. Например, $$$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120$$$.

$$$^\ddagger$$$ Если $$$a$$$ и $$$b$$$ — целые числа, то $$$a$$$ кратно $$$b$$$, если существует целое число $$$c$$$ такое, что $$$a = b \cdot c$$$. Например, $$$10$$$ кратно $$$5$$$, но $$$9$$$ не кратно $$$6$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Единственная строка каждого набора входных данных содержит одно целое число $$$k$$$ ($$$2 \le k \le 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — наибольшее возможное натуральное число $$$x$$$, удовлетворяющее условиям выше.

Если такого $$$x$$$ не существует, выведите $$$-1$$$.

Пример
Входные данные
4
3
6
8
10
Выходные данные
2
5
7
9
Примечание

В первом наборе $$$2! + 1! = 2 + 1 = 3$$$, что кратно $$$3$$$.

В третьем наборе $$$7! + 6! = 5040 + 720 = 5760$$$, что кратно $$$8$$$.