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: MEDIUM_HARD
Tags: Number theory

Mathematics

Probability

Starter code:

Solutions:
import math
for t in range(int(input())):
	n = int(input())
	ans = 0
	x = math.floor(math.sqrt(n))
	i = 1
	while i <= x:
		ans += n // i
		i += 1
	ans *= 2
	ans -= x ** 2
	num = int(ans)
	den = n * n
	g = math.gcd(num, den)
	print('%d/%d' % (num // g, den // g))


from collections import defaultdict
import sys
import math as m
import random as rd
import bisect as b
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()
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 math import gcd, sqrt

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	tot = n * n
	m = 1 + int(sqrt(n))
	s = 0
	for d in range(1, m):
		s += n // d
	s += s
	s -= (m - 1) * (m - 1)
	g = gcd(s, tot)
	print(str(s // g) + '/' + str(tot // g))


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
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))


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)


import math
import sys
from fractions import Fraction

def next_int():
	return int(input())

def one_test(n):
	root = math.floor(math.sqrt(n))
	ans = 2 * sum((n // k for k in range(1, root + 1))) - root * root
	return Fraction(ans, n * n)

def proper_fraction(f):
	ret = str(f)
	if f.denominator == 1:
		ret += '/1'
	return ret
t = next_int()
for i in range(t):
	res = one_test(next_int())
	print(proper_fraction(res))


from math import gcd, sqrt

def showABprob(num):
	trial = num * num
	lim = int(sqrt(num))
	succ = 2 * sum((num // div for div in range(1, lim + 1)))
	succ -= lim * lim
	g = gcd(succ, trial)
	print(f'{succ // g}/{trial // g}')
T = int(input())
for ti in range(T):
	showABprob(int(input()))


from math import gcd
T = int(input())
for ti in range(T):
	N = int(input())
	trial = N * N
	succ = 0
	div = 1
	while N >= div * div:
		succ += (N // div - div) * 2 + 1
		div += 1
	g = gcd(succ, trial)
	print(f'{succ // g}/{trial // g}')


def gcd(a, b):
	if a * b == 0:
		return 0
	while b:
		(a, b) = (b, a % b)
	return a

def isqrt(num):
	bits = (num.bit_length() - 1) // 2
	lo = int(2 ** bits)
	hi = 2 ** (bits + 1)
	while hi - lo > 1:
		md = (hi + lo) // 2
		if md * md > num:
			hi = md
		else:
			lo = md
	return lo

def showABprob(num):
	trial = num * num
	lim = isqrt(num)
	succ = sum((num // div for div in range(1, lim + 1)))
	succ = 2 * succ - lim * lim
	g = gcd(succ, trial)
	print(f'{succ // g}/{trial // g}')
T = int(input())
for ti in range(T):
	showABprob(int(input()))


from math import gcd, sqrt
t = int(input())
for i in range(t):
	n = int(input())
	c = n * n
	l = int(sqrt(n))
	s = 2 * sum((n // d for d in range(1, l + 1)))
	s -= l * l
	g = gcd(s, c)
	print(f'{s // g}/{c // g}')