Một bài toán cực đơn giản cho HS tiểu học.

Cho một số nguyên dương \(k\).

Nhiệm vụ của bạn là tìm số nguyên dương \(x\) lớn nhất thỏa mãn \(1 \le x < k\) sao cho \(x! + (x-1)!^\dagger\) chia hết cho \(k\).

\(^\dagger\) \(y!\) được định nghĩa như sau: \(y!=1\times 2 \times 3 \times \ldots \times y\). Tuy nhiên, hãy lưu ý rằng \(0!=1\). Ví dụ \(5!=5\times 4 \times 3 \times 2 \times 1=120\).

Input

• Dòng thứ nhất chứa \(t\) \((t \leq 10^6)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\) \((k \leq 10^{18})\).

Output

• Ứng với mỗi câu hỏi in ra đáp án thỏa mãn. Nếu không có \(x\) nào thỏa mãn, in ra \(\texttt{-1}\).

Scoring

• 30% test có \(t \le 100\);
• 70% test còn lại: không ràng buộc gì thêm.
• Lưu ý: Chia subtask cho mục đích giải trí, bạn không thể cày trâu bài này được đâu ahihi

Example

2
2
1

1
-1