import sys from fractions import Fraction def main(): input = sys.stdin.read().split() idx = 0 T = int(input[idx]) idx +=1 for _ in range(T): N = int(input[idx]) idx +=1 primes = list(map(int, input[idx:idx+N])) idx +=N # Precompute expected values for all subsets of primes (up to N=13) # We can represent each composite as a bitmask of primes from functools import lru_cache primes = tuple(sorted(primes)) P = 1 for p in primes: P *= p @lru_cache(maxsize=None) def euler_phi(mask): res = 1 for i in range(len(primes)): if mask & (1 << i): res *= primes[i] -1 return res @lru_cache(maxsize=None) def denominator(mask): res = 1 for i in range(len(primes)): if mask & (1 << i): res *= primes[i] return res @lru_cache(maxsize=None) def compute_e(mask): n = bin(mask).count('1') if n ==0: return Fraction(0) if n ==1: return Fraction(1) P_den = denominator(mask) if P_den ==1: return Fraction(0) phi = euler_phi(mask) # Compute the probability of each case # Case 1: r divides P (gcd(r,P) = P) prob_gcd_P = Fraction(1, denominator(mask)) # Case 2: r divides a non-trivial divisor divisors = [] from itertools import combinations bits = [i for i in range(len(primes)) if (mask & (1 << i))] total_non_trivial =0 non_trivial_prob = Fraction(0) for k in range(1, n): for subset in combinations(bits, k): sub_mask = 0 for b in subset: sub_mask |= 1<