100000044 - Round 842 1768A 最大凸出
找到一个尽可能大的整数x,使得其1 ≤ x < k 并且x!+(x-1)!能够整除k。
Input
第一行，一个整数t。
接下来t行，每行一个整数k_i。
对于100%的数据：
1\le t \le 10^4
2 \le k_i \le 10^9
Output
对于每个k_i，输出一行一个整数，表示最大的x，若不存在这样的x，输出-1。
Examples
Input
4 3 6 8 10
Output
2 5 7 9
找到一个尽可能大的整数x,使得其1 ≤ x < k 并且x!+(x-1)!能够整除k。
第一行，一个整数t。
接下来t行，每行一个整数k_i。
对于100%的数据：
1\le t \le 10^4
2 \le k_i \le 10^9
对于每个k_i，输出一行一个整数，表示最大的x，若不存在这样的x，输出-1。
4 3 6 8 10
2 5 7 9