D. "逆"天求和
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

董事长最近学了"逆元"，他现在来问你，对于每一个质数 p 来讲，我们假设 f(x) 是 x 的逆元，那么 等于多少。

如果你不理解上述式子的意思，那么可以表述为，从 1 到 p - 1 的所有整数的逆元的和

逆元定义如下：

对于一个数 p ，我们在此题中，仅仅考虑 p 是质数。

若对于一个整数 a ，存在一个 0 到 p - 1 的整数 b，使得 ,也就是 a、b 的乘积对 p 取模等于 1。那么我们说 a, b 在模 p 情况下互为逆元。

你看了一眼，不太会。但是你感觉这是一个数学题，于是你去问了胡老板，胡老板撇了一眼，一脸不屑的说："这也算数学题，我给你一句提示，你自己领悟吧"

胡老板说的是：在模 p 情况下，对于每一个不为 0 的整数 a，存在唯一一个整数 ,他们互为逆元。

一共有T组询问 数据范围：q ≤ 100000，T ≤ 9592

Input

第一行一个正整数T，表示一共有T次询问 对于每次询问，每行一个正质数p

Output

每次询问输出一个正整数，表示从1到p - 1中的每个数在模p意义下的逆元的和

Example
Input
2
5
99991
Output
10
4999050045