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

Difficulty: interview

Starter code:

Solutions:
import math
for _ in range(int(input())):
 n=int(input())
 s=int(math.sqrt(n))
 ans=0
 for i in range(1,s+1):
  ans+=(n//i)
 ans=ans*2-(s*s)
 g=math.gcd(n*n,ans)
 print(str(ans//g)+"/"+str(n*n//g)) 

from collections import defaultdict
import sys
import math as m
import random as rd
import bisect as b
#import numpy as np
import time
sys.setrecursionlimit(1000000)


def uno(): return int(sys.stdin.readline().strip())


def dos(): return sys.stdin.readline().strip()


def tres(): return list(map(int, sys.stdin.readline().strip().split()))


def cuatro(): return sys.stdin.readline().strip().split()

################## CODE STARTS FROM HERE ######################


for _ in range(uno()):
 n = uno()
 ans, root = 0, m.floor(m.sqrt(n))
 for i in range(1, root+1):
  ans += n//i
 ans = ans+ans-root*root
 a, b = ans//m.gcd(ans, n*n), (n*n)//m.gcd(ans, n*n)
 print(str(a)+"/"+str(b))


from collections import defaultdict
import sys
import math as m
import random as rd
import bisect as b
#import numpy as np
import time
sys.setrecursionlimit(1000000)


def uno(): return int(sys.stdin.readline().strip())


def dos(): return sys.stdin.readline().strip()


def tres(): return map(int, sys.stdin.readline().strip().split())


def cuatro(): return sys.stdin.readline().strip().split()

################## CODE STARTS FROM HERE ######################


for _ in range(uno()):
 n = uno()
 ans, root = 0, m.floor(m.sqrt(n))
 for i in range(1, root+1):
  ans += n//i
 ans = ans+ans-root*root
 a, b = ans//m.gcd(ans, n*n), (n*n)//m.gcd(ans, n*n)
 print(str(a)+"/"+str(b))

import math

def solve():
 n = int(input())
 num = 0

 denom = n * n
 s = int(math.sqrt(n))
 for i in range(1, s + 1):
  num += n//i

 num = (2 * num) - (s * s)
 k = math.gcd(num, denom)

 print(str(num//k) + "/" + str(denom//k)) 

t = int(input())


for tt in range(0, t):
 solve()

import math

def solve():
 n = int(input())
 num = 0

 denom = n * n
 s = int(math.sqrt(n))
 for i in range(1, s + 1):
  num += n//i

 num = (2 * num) - (s * s)
 k = math.gcd(num, denom)

 print(str(num//k) + "/" + str(denom//k)) 

t = int(input())


for tt in range(0, t):
 solve()

def gcd(a,b):
 if b==0: return a 
 return gcd(b,a%b)
from math import sqrt as S 
for _ in range(int(input())):
 n=int(input())
 tot=n*n
 s=0
 beta=int(S(n))
 for i in range(1,int(S(n))+1):
  s+=n//i 
 s=2*s-beta*beta 
 g=gcd(s,tot)
 s=s//g 
 tot=tot//g 
 print(s,end='')
 print('/',end='')
 print(tot)