5346 - 数论：威尔逊定理：最大素数Q
Time Limit : 1 秒
Memory Limit : 64 MB
给出一个素数P，找出小于P的最大素数Q，并计算Q的阶乘对P取模的结果
Input
这段话描述了一个数学或编程问题中的输入格式。 第一行包含一个数字 T（1≤T≤10），表示测试用例的数量。
接下来是 T 行，每行都包含一个正质数 P（1e9≤p≤1e14）
Output
对于每个测试用例，输出一个整数，表示 Q 的阶乘模 P 的结果。 一行一个答案
Examples
Input
1 1000000000007
Output
493789707473