Problem: 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<=10^3
1<=N<=10^9

Solution (in PYTHON):

Solution:
from fractions import gcd
from sys import stdin


def p(n):
    s = int(n ** .5)
    c = sum(n/i for i in xrange(1, s+1)) * 2 - s**2
    g = gcd(c, n ** 2)
    return '{}/{}'.format(c / g, n**2 / g)


print(
    '\n'.join(
        p(int(ln))
        for i, ln in enumerate(stdin) if i
    )
)