code chef

czhtr

　　


All submissions for this problem are available.
　　

Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor(GCD) of A and B equals
to B.


Input


The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a single integer N on a separate line.


Output


For each test case, output a single line containing probability as an irreducible fraction.

Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor(GCD) of A and B equals
to B.


Input


The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a single integer N on a separate line.


Output


For each test case, output a single line containing probability as an irreducible fraction.


Example

Input:
3
1
2
3
Output:
1/1
3/4
5/9


Constraints


1<=T<=103



1<=N<=109


　　本题也是个数学题。
　　有两个知识点：
　　1 求最大公约数的算法
　　2 求小于等于一个数&#20540;的两数相乘的对数 - 这个又是数学公式
　　


　　据说这里是数学详细解析，感兴趣的研究一下：
　　http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4204.pdf


　　OJ系统：
　　http://www.codechef.com/problems/COOLGUYS/


　　long long mGcd(long long a, long long b)
{
long long c = 0;
while (b)
{
c = b;
b = a % b;
a = c;
}
return c;
}
long long pairsOfCoolguys(long long n)
{
long long ans = 0;
long long sq = (long long)sqrt(n);
for (unsigned i = 1; i <= sq; i++)
{
ans += n/i;
}
ans = (ans<<1) - sq*sq;
return ans;
}
void coolguys()
{
long long n = 0;
int T = 0;
cin>>T;
while (T--)
{
cin>>n;
long long ps = pairsOfCoolguys(n);
n *= n;
long long d = mGcd(ps, n);
cout <<(ps/d) << &quot;/&quot;<<(n/d)<<&quot;\n&quot;;
}
}