You are given an array A consisting of N positive integers.

Suppose F(B,X) gives the minimum positive integer Y such that:
X divides Y \cdot B_{i} for all (1 ≤ i ≤ |B|).

Find the value of F(A,A_{i}) for all (1 ≤ i ≤ N). 

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N — the length of the array A.
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N} representing the array A.

------ Output Format ------ 

For each test case, print N space-separated integers where the i^{th} integer denotes the value F(A,A_{i}). 

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
2
1 2
3
2 2 2

----- Sample Output 1 ------ 
1 2
1 1 1

----- explanation 1 ------ 
Test case $1$: Given $A = [1, 2]$
- $F(A, A_{1}) = F(A, 1) = 1$: Here $X = 1$ and $Y = 1$ as $X = 1$ divides both $Y\cdot A_{1} = 1$ and $Y\cdot A_{2} = 2$.
- $F(A, A_{2}) = F(A, 2) = 2$: Here $X = 2$ and $Y = 2$ as $X = 2$ divides both $Y\cdot A_{1} = 2$ and $Y\cdot A_{2} = 4$.

Note that the values of $Y$ are minimum possible for both $F(A, A_{1})$ and $F(A, A_{2})$.

Test case $2$: Given $A = [2, 2, 2]$
- $F(A, A_{1}) = F(A, 2) = 1$: Here $X = 2$ and $Y = 1$ as $X = 1$ divides $Y\cdot A_{1} = 2, Y\cdot A_{2} = 2,$ and $Y\cdot A_{3} = 2$.
- $F(A, A_{2}) = F(A, 2) = 1$: Here $X = 2$ and $Y = 1$ as $X = 1$ divides $Y\cdot A_{1} = 2, Y\cdot A_{2} = 2,$ and $Y\cdot A_{3} = 2$.
- $F(A, A_{3}) = F(A, 2) = 1$: Here $X = 2$ and $Y = 1$ as $X = 1$ divides $Y\cdot A_{1} = 2, Y\cdot A_{2} = 2,$ and $Y\cdot A_{3} = 2$.

Note that the values of $Y$ are minimum possible for $F(A, A_{1}), F(A, A_{2}),$ and $F(A, A_{3})$.

Source: codechef | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions:
import math as m
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	gcd = A[0]
	for j in A:
		gcd = m.gcd(j, gcd)
	for j in A:
		print(j // gcd, end=' ')
	print()


import math
test = int(input())
for t in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	gcd = 0
	for i in range(n):
		gcd = math.gcd(gcd, arr[i])
	for i in range(n):
		print(arr[i] // gcd, end=' ')
	print()


def kou(s, h):
	while h != 0:
		(s, h) = (h, s % h)
	return s
for _ in range(int(input())):
	i = int(input())
	k = list(map(int, input().split()))
	r = k[0]
	for o in k:
		r = kou(r, o)
	for o in k:
		print(o // r, end=' ')
	print()


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
for test_case in range(int(input())):
	array_length = int(input())
	array = list(map(int, input().split()))
	gcd_value = array[0]
	for element in array:
		gcd_value = gcd(gcd_value, element)
	for element in array:
		print(element // gcd_value, end=' ')
	print()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	f = A[0]
	for i in range(1, n):
		f = gcd(f, A[i])
	res = list()
	for i in A:
		res.append(i // f)
	print(*res)


import math
t = int(input())
for x in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	final_gcd = a[0]
	for i in a:
		final_gcd = math.gcd(final_gcd, i)
	for i in a:
		print(i // final_gcd, end=' ')
	print()


def gcd(x, y):
	c = x
	x = max(x, y)
	y = min(c, y)
	c = x % y
	while c != 0:
		x = y
		y = c
		c = x % y
	return y

def big_gcd(a):
	v = a[0]
	for i in range(1, len(a)):
		v = gcd(v, a[i])
	return v
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	G = big_gcd(a)
	arr = [str(e // gcd(e, G)) for e in a]
	print(' '.join(arr))


import math
t = int(input())
for i in range(t):
	x = int(input())
	list1 = list(map(int, input().split()))
	hcf = 0
	for i in range(len(list1)):
		hcf = math.gcd(hcf, list1[i])
	for i in list1:
		print(i // hcf, end=' ')
	print()


def gcd(y, x):
	if x == 0:
		return y
	return gcd(x, y % x)
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = input().split()
	for i in range(len(a)):
		a[i] = int(a[i])
	div = a[0]
	for i in range(1, len(a)):
		div = gcd(div, a[i])
	out = []
	for el in a:
		print(int(el / div), end=' ')
	print()


import math
for i in range(int(input())):
	n = int(input())
	flag = 0
	arr = list(map(int, input().split()))
	d = arr[0]
	for i in arr:
		d = math.gcd(d, i)
	for i in arr:
		print(i // d, end=' ')
	print()


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = [0] * n
	l = a[0]
	for j in range(1, n):
		l = math.gcd(l, a[j])
	ans = [0] * n
	for i in range(n):
		ans[i] = a[i] // l
	print(*ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	final_gcd = a[0]
	for i in a:
		final_gcd = math.gcd(final_gcd, i)
	for i in a:
		print(i // final_gcd, end=' ')
	print()


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	for __ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		res = l[0]
		for i in range(1, len(l)):
			res = find_gcd(res, l[i])
		for i in l:
			print(i // res, end=' ')
		print('\n')
main()


import math as m
z = int(input())
while z > 0:
	z -= 1
	a = int(input())
	b = list(map(int, input().split()))
	c = b[0]
	for i in b:
		c = m.gcd(c, i)
	for i in b:
		print(i // c, end=' ')
	print()


import numpy as np
t = int(input())
for r in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	arr = np.array(a)
	g = np.gcd.reduce(arr)
	l = []
	for i in range(n):
		print(a[i] // g, end=' ')
	print('')


import numpy as np

def lcm(arr, idx=0):
	if idx == len(arr) - 1:
		return arr[idx]
	a = arr[idx]
	b = lcm(arr, idx + 1)
	return int(a * b / m.gcd(a, b))
t = int(input())
for r in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	arr = np.array(a)
	g = np.gcd.reduce(arr)
	l = []
	for i in range(n):
		print(a[i] // g, end=' ')
	print('')


import math
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	m = b[0]
	for i in b:
		m = math.gcd(m, i)
	for i in b:
		print(i // m, end=' ')
	print()


from functools import reduce

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

def div_by(a):
	return lambda x: x // a
t = int(input())
for t_ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	arr_gcd = reduce(gcd, A)
	ans = map(div_by(arr_gcd), A)
	for i in ans:
		print(i, end=' ')
	print()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	g = ar[0]
	for i in ar:
		g = math.gcd(g, i)
	for i in ar:
		print(i // g, end=' ')
	print()


import math
T = int(input())
for x in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for i in a:
		g = math.gcd(i, g)
	for i in a:
		print(i // g, end=' ')
	print('')


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	GCD = a[0]
	for x in a:
		GCD = math.gcd(x, GCD)
	for x in a:
		ans = x // GCD
		print(ans, end=' ')
	print('')


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	final_gcd = A[0]
	for i in A:
		final_gcd = math.gcd(final_gcd, i)
	for i in A:
		print(i // final_gcd, end=' ')
	print()


import math
from typing import Sequence

def div_by_a_i(a: Sequence[int]) -> Sequence[int]:
	gcd = a[0]
	for i in a:
		gcd = math.gcd(gcd, i)
	result = [i // gcd for i in a]
	return result
t = int(input())
for _ in range(t):
	unused_n = input()
	a = [int(x) for x in input().split()]
	result = div_by_a_i(a)
	print(' '.join((str(x) for x in result)))


for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	from math import gcd
	ans = []
	g = arr[0]
	for i in range(1, n):
		g = gcd(g, arr[i])
	for i in arr:
		ans.append(i // g)
	print(*ans)


from math import *
t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in l:
		g = gcd(g, i)
	for i in l:
		print(i // g, end=' ')
	print()
	t -= 1


def fun(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	gcd = a[0]
	for i in range(1, n):
		gcd = fun(max(gcd, a[i]), min(gcd, a[i]))
	l = [x // gcd for x in a]
	print(*l)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	g = arr[0]
	for i in range(n):
		g = gcd(g, arr[i])
	for i in arr:
		print(i // g, end=' ')
	print('\n')


from math import *

def solve(n, l):
	g = l[0]
	for i in range(1, n):
		g = gcd(g, l[i])
	for i in range(n):
		l[i] = l[i] // g
	return l
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(*solve(n, l))


import math
for i in range(int(input())):
	num = int(input())
	lis = list(map(int, input().split(' ')))
	c = 0
	for j in lis:
		c = math.gcd(c, j)
	for j in range(num):
		print(lis[j] // c, end=' ')
	print()


def hcf(a, b):
	if b == 0:
		return a
	return hcf(b, a % b)

def list_hcf(mylist):
	h = mylist[0]
	for i in range(1, len(mylist)):
		h = hcf(h, mylist[i])
		if h == 1:
			return 1
	return h
t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	h = list_hcf(list1)
	for val in list1:
		print(val // h, end=' ')
	print()


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
from math import gcd
from functools import reduce

def gcdl(A):
	return reduce(gcd, A)
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	g = gcdl(A)
	ans.append([a // g for a in A])
outpltlt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))

def gcd(a, b):
	return gcd(b, a % b) if a % b else b
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	g = A[0]
	for a in A[1:]:
		g = gcd(a, g)
	ans.append([a // g for a in A])
outpltlt(ans)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	gcd = max(a)
	for i in range(n):
		gcd = math.gcd(a[i], gcd)
	for i in range(n):
		print(a[i] // gcd, end=' ')
	print()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	g = a[0]
	for i in range(1, n):
		g = gcd(g, a[i])
	for i in range(n):
		print(a[i] // g, end=' ')
	print()


import math
for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	l = []
	ans = 0
	for i in m:
		ans = math.gcd(ans, i)
	for i in m:
		l.append(i // ans)
	print(*l)


import math

def gc(x, y):
	b = max(x, y)
	a = min(x, y)
	while b % a != 0:
		(a, b) = (b % a, a)
	return a

def gcd(l):
	hcf = 1
	if len(l) == 1:
		return l[0]
	(x, y) = (l[0], l[1])
	hcf = gc(x, y)
	for i in range(2, len(l)):
		hcf = gc(hcf, l[i])
	return hcf
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = [1] * N
	y = gcd(A)
	for i in range(N):
		print(A[i] // y, end=' ')
	print()


from math import *
t = int(input())
while t > 0:
	a = int(input())
	x = list(map(int, input().split()))
	g = x[0]
	for i in x:
		g = gcd(g, i)
	for i in x:
		print(i // g, end=' ')
	print()
	t -= 1


from math import gcd
t = int(input())
while t:
	N = int(input())
	arr = list(map(int, input().split()))
	ans = []
	g = gcd(arr[0], arr[1])
	for i in range(2, N):
		g = gcd(g, arr[i])
	for x in arr:
		ans.append(x // g)
	print(*ans)
	t = t - 1


import math
n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	s = min(l)
	c = 0
	for i in l:
		s = math.gcd(s, i)
	for i in l:
		print(i // s, end=' ')
	print()


import math
a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	p = 0
	for j in range(0, b):
		p = math.gcd(p, c[j])
	for k in c:
		print(k // p, end=' ')
	print()


from math import gcd
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	p = 0
	for i in range(0, n):
		p = gcd(p, a[i])
	for i in a:
		print(i // p, end=' ')
	print()


def gcd(x, y):
	while x != y:
		if x > y:
			x -= (x - 1) // y * y
		else:
			y -= (y - 1) // x * x
	return x
for z in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	val = lst[0]
	for i in range(n):
		val = gcd(val, lst[i])
	for i in range(n):
		print(lst[i] // val, end=' ')
	print()


import math
t = int(input())
for a in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = l[0]
	for i in l:
		x = math.gcd(x, i)
	for j in l:
		print(j // x, end=' ')
	print()


from math import *

def find_gcd(a, b):
	return gcd(a, b)
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	num1 = l[0]
	num2 = l[1]
	gcd1 = find_gcd(num1, num2)
	for i in range(2, len(l)):
		gcd1 = find_gcd(gcd1, l[i])
	for i in range(n):
		print(l[i] // gcd1, end=' ')
	print()


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	y = []
	r = l[0]
	for k in range(n):
		r = math.gcd(r, l[k])
	for j in range(n):
		p = l[j]
		q = math.gcd(p, r)
		yy = p // q
		y.append(yy)
	print(*y)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))

	def gcd(my_list):
		result = my_list[0]
		for x in my_list[1:]:
			if result < x:
				temp = result
				result = x
				x = temp
			while x != 0:
				temp = x
				x = result % x
				result = temp
		return result
	x = gcd(a)
	for i in a:
		print(i // x, end=' ')
	print()


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in l:
		g = gcd(g, i)
	for i in l:
		print(i // g, end=' ')
	print()


from math import *
testinputt = int(input())
while testinputt > 0:
	noo = int(input())
	listt = list(map(int, input().split()))
	gg = listt[0]
	for i in listt:
		gg = gcd(gg, i)
	for i in listt:
		print(i // gg, end=' ')
	print()
	testinputt -= 1


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in l:
		g = gcd(g, i)
	for i in l:
		print(i // g, end=' ')
	print()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	hi = 0
	for i in range(n):
		hi = math.gcd(hi, lst[i])
	for i in range(n):
		print(lst[i] // hi, end=' ')
	print(' ')