After solving some Graph Theory related problems KBG challenged Sameer to solve the following problem.

There is an undirected graph consisting of N vertices numbered from 1 to N.

For every pair of vertices u and v (u \neq v) in the graph, there is a undirected weighted edge between u and v if and only if u divides v, with weight \frac{v}{u}. Note that such a graph will not have self loops or multiple edges.

You must answer Q queries. In each query you are given two vertices u and v. You must find the minimum distance from vertex u to vertex v.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q — the number of vertices and the number of queries.
- The next Q lines contain two space-separated integers u and v — vertices corresponding to the query.

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

For each test case, print Q lines — the answers to the Q queries.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$ 
$1 ≤ Q ≤ 10^{5}$
$1 ≤ u , v ≤ N$
- The sum of $N$ over all test cases does not exceed $10^{5}$.
- The sum of $Q$ over all test cases does not exceed $10^{5}$.

------ subtasks ------ 

Subtask 1 (100 points): Original Constraints.

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

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

----- explanation 1 ------ 
Test case 1: Given $N = 6$ and $2$ queries..
- In the first query, $u = 3$ and $v = 6$. So there is an edge from $6$ to $3$ with weight $2$. we can use that path and minimum cost will be $2$.

- In the second query, $u = 2$ and $v = 3$. So there is an edge from $2$ to $1$ with weight $2$ and from $3$ to $1$ with weight $3$. we can use that path $(2 \rightarrow 1 \rightarrow 3)$ and minimum cost will be $5$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
from collections import defaultdict

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

def cal(a):
	res = 0
	temp = 100001 ** 0.5
	temp = int(temp) + 1
	i = 2
	while a > 1:
		while a % i == 0:
			res += i
			a //= i
		if i == 2:
			i += 1
		else:
			i += 2
		if i > temp and a > 1:
			res += a
			return res
	return res
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(a, b) = map(int, input().split())
		g = gcd(a, b)
		if a == b:
			print(0)
		elif a == 1 or b == 1:
			print(max(cal(a), cal(b)))
		else:
			print(cal(a // g) + cal(b // g))


def hel2(x, y):
	if x == y:
		return 0
	l = []
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			l.append(i)
			l.append(x // i)
			if i * i == x:
				l.pop()
	l.sort(reverse=True)
	cnt = 0
	prev = x
	for i in range(1, len(l)):
		if prev % l[i] == 0 and l[i] % y == 0:
			cnt += prev // l[i]
			prev = l[i]
			if l[i] == y:
				break
	return cnt

def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)

def fun(n, u, v):
	g = gcd(u, v)
	res1 = hel2(u, g)
	res2 = hel2(v, g)
	res = res1 + res2
	return res
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for _ in range(q):
		(u, v) = map(int, input().split())
		print(fun(n, u, v))


from math import gcd
t = int(input())
for k in range(t):
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		g = gcd(u, v)
		u //= g
		v //= g
		ans = 0
		for i in [u, v]:
			while i % 2 == 0:
				i = i // 2
				ans += 2
			for j in range(3, i + 1):
				if j * j > i:
					break
				while i % j == 0:
					i = i // j
					ans += j
			if i > 1:
				ans += i
		print(ans)


def gcd(a, b):
	c = a
	a = max(a, b)
	b = min(c, b)
	while b != 0:
		c = a % b
		a = b
		b = c
	return a

def prime_sum(x):
	if x == 1:
		return 0
	i = 2
	s = 0
	while i * i <= x:
		while x % i == 0:
			s += i
			x //= i
		i += 1
	if x != 1:
		s += x
	return s
for t in range(int(input())):
	(n, q) = map(int, input().split())
	for e in range(q):
		(u, v) = map(int, input().split())
		g = gcd(u, v)
		(u, v) = (u // g, v // g)
		print(prime_sum(u) + prime_sum(v))


import sys
import os
import math
import collections

def primeFactors(n):
	result = []
	while n % 2 == 0:
		result.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			result.append(i)
			n = n / i
	if n > 2:
		result.append(n)
	result.sort()
	return result
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	for _ in range(M):
		(P, Q) = map(int, input().split())
		A = primeFactors(P)
		B = primeFactors(Q)
		C = collections.Counter(A)
		D = collections.Counter(B)
		C.subtract(D)
		val = 0
		for i in C.items():
			val += int(i[0] * abs(i[1]))
		print(val)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	for j in range(m):
		(u, v) = map(int, input().split())
		fac = math.gcd(u, v)
		x = u // fac
		y = v // fac
		ans = 0
		for i in [x, y]:
			j = 2
			while j * j <= i:
				while i % j == 0:
					ans += j
					i //= j
				j += 1
			if i > 1:
				ans += i
		print(ans)


from math import gcd
t = int(input())
for _ in range(t):
	(vertices, queries) = map(int, input().split())
	while queries > 0:
		queries -= 1
		(u, v) = map(int, input().split())
		g = gcd(u, v)
		u = u // g
		v = v // g
		i = 2
		ans = 0
		while i * i <= u:
			while u % i == 0:
				ans += i
				u = u // i
			i += 1
		if u > 1:
			ans += u
		i = 2
		while i * i <= v:
			while v % i == 0:
				ans += i
				v = v // i
			i += 1
		if v > 1:
			ans += v
		print(ans)


from math import gcd

def fun(i):
	ans = 0
	for j in range(2, i + 1):
		if j * j > i:
			break
		while i % j == 0:
			i = i // j
			ans += j
	if i > 1:
		ans += i
	return ans
for k in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		g = gcd(u, v)
		u //= g
		v //= g
		ans = fun(u) + fun(v)
		print(ans)


def gcd(a, b):
	if a == 0:
		return abs(b)
	else:
		return gcd(b % a, a)
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		g = gcd(u, v)
		u //= g
		v //= g
		res = 0
		for x in [u, v]:
			for i in range(2, x + 1):
				if i * i > x:
					break
				while x % i == 0:
					x //= i
					res += i
			if x > 1:
				res += x
		print(res)


import math
l = []
for i in range(3, 100001, 2):
	t = 1
	for j in range(3, int(math.sqrt(i)) + 1, 2):
		if i % j == 0:
			t = 0
			break
	if t == 1:
		l.append(i)
a = [0] * 100001
for i in range(2, 100001):
	if i % 2 == 0:
		a[i] = a[i // 2] + 2
	j = 0
	while l[j] <= math.sqrt(i) + 1:
		if i % l[j] == 0:
			a[i] = a[i // l[j]] + l[j]
			break
		j += 1
	if a[i] == 0:
		a[i] = i
for i in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		r = math.gcd(u, v)
		print(a[u] + a[v] - 2 * a[r])


from math import gcd
N = int(100000.0) + 69
s = list(range(N + 1))
for i in range(2, int(N ** 0.5) + 1):
	if s[i] == i:
		for j in range(i * i, N, i):
			if s[j] == j:
				s[j] = i

def factors_sum(X):
	res = 0
	while X > 1:
		res += s[X]
		X //= s[X]
	return res
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for _ in range(q):
		(u, v) = map(int, input().split())
		print(factors_sum(u // gcd(u, v)) + factors_sum(v // gcd(u, v)))


import math
T = int(input())
for t in range(T):
	(n, q) = map(int, input().split())
	s = [0 for i in range(n + 1)]

	def sieve():
		for i in range(1, n + 1):
			if i % 2 == 1:
				s[i] = i
			else:
				s[i] = 2
		for i in range(3, math.ceil(math.sqrt(n + 1)), 2):
			if s[i] == i:
				for j in range(i * i, n + 1, i):
					if s[j] == j:
						s[j] = i

	def getFactorization(x):
		ret = []
		while x != 1:
			ret.append(s[x])
			x = x // s[x]
		return ret
	sieve()

	def dis(a, b):
		if a >= b:
			c = a // b
		else:
			c = b // a
		l = getFactorization(c)
		return sum(l)
	for i in range(q):
		(u, v) = map(int, input().split())
		if u == v:
			print(0)
		elif u % v == 0 or v % u == 0:
			print(dis(u, v))
		else:
			c = math.gcd(u, v)
			print(dis(u, c) + dis(v, c))


def factors(n):
	ans = 0
	while n % 2 == 0:
		ans += 2
		n //= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			ans += i
			n //= i
	if n > 2:
		ans += n
	return ans
from math import gcd
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		g = gcd(u, v)
		(u, v) = (u // g, v // g)
		print(factors(u) + factors(v))


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import math, heapq, bisect
import math as mt
input = stdin.readline

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def gcd(a, b):
	return math.gcd(a, b)

def gcd_list_of_elements(li):
	n = len(li)
	res = li[0]
	for i in range(1, n):
		res = math.gcd(res, li[i])
	return res

def isPalindrome(x):
	x = str(x)
	return x == x[::-1]
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def function(num, x):
	cnt = 0
	while num % x == 0:
		cnt += 1
		num //= x
	return cnt * x

def get_cost(num):
	if num == 1:
		return 0
	cost = 0
	factors = set(getFactorization(num))
	for factor in factors:
		cost += function(num, factor)
	return cost
sieve()
t = int(input().strip())
for _ in range(t):
	(n, q) = list(map(int, input().strip().split()))
	for _ in range(q):
		(u, v) = list(map(int, input().strip().split()))
		g = gcd(u, v)
		ans = get_cost(u // g) + get_cost(v // g)
		print(ans)


import math

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

def fun(g, n):
	ans = 0
	n = n // g
	if n == 1:
		return 0
	while n % 2 == 0:
		ans += 2
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans += i
			n = n // i
	if n > 2:
		ans += n
	return ans
for t in range(int(input())):
	(n, qu) = list((int(i) for i in input().split()))
	for q in range(qu):
		(u, v) = list((int(i) for i in input().split()))
		g = gcd(u, v)
		ans = fun(g, u) + fun(g, v)
		print(ans)


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def find():
	m1 = 100001
	f1 = [0 for i in range(m1)]
	f1[1] = 1
	for i in range(2, m1):
		f1[i] = i
	for i in range(4, m1, 2):
		f1[i] = 2
	for i in range(3, 317):
		if f1[i] == i:
			for j in range(i * i, m1, i):
				if f1[j] == j:
					f1[j] = i
	return f1
f1 = find()

def solve(a):
	dic = defaultdict(lambda : 0)
	while a != 1:
		dic[f1[a]] += 1
		a = a // f1[a]
	return dic
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	(count1, count2) = ([], [])
	for i in range(n):
		count1.append(i)
	for i in range(n):
		count1.append(i)
	for i in range(q):
		(a, b) = list(map(int, input().split()))
		a1 = solve(a)
		b1 = solve(b)
		ans = set(list(a1.keys()) + list(b1.keys()))
		for i in ans:
			temp = min(a1[i], b1[i])
			a1[i] -= temp
			b1[i] -= temp
		res = 0
		for i in ans:
			res += i * (a1[i] + b1[i])
		print(res)
	for i in range(n):
		count2.append(i)
	for j in range(n):
		count2.append(j)


from math import ceil, sqrt
from collections import defaultdict

def spffunc():
	lim = 10 ** 5
	s = [0] * lim
	s[1] = 1
	for i in range(2, lim):
		s[i] = i
	for i in range(4, lim, 2):
		s[i] = 2
	for i in range(3, ceil(sqrt(lim))):
		if s[i] == i:
			for l in range(i * i, lim, i):
				if s[l] == l:
					s[l] = i
	return s
spf = spffunc()

def gpf(n):
	gpfdict = defaultdict(int)
	while n != 1:
		gpfdict[spf[n]] += 1
		n = n // spf[n]
	return gpfdict
for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	for i1 in range(b):
		op = 0
		(u, v) = [int(i) for i in input().split()]
		u = gpf(u)
		v = gpf(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i2 in x:
			if u[i2] > v[i2]:
				m = v[i2]
			else:
				m = u[i2]
			u[i2] -= m
			v[i2] -= m
		for i3 in x:
			op += i3 * (u[i3] + v[i3])
		print(op)


import math
from collections import defaultdict

def check1():
	maxi = 100001
	df = [0] * maxi
	df[1] = 1
	for i in range(2, maxi):
		df[i] = i
	for i in range(4, maxi, 2):
		df[i] = 2
	for i in range(3, math.ceil(math.sqrt(maxi))):
		if df[i] == i:
			for j in range(i * i, maxi, i):
				if df[j] == j:
					df[j] = i
	return df
df = check1()

def check2(k):
	m = defaultdict(lambda : 0)
	while k != 1:
		m[df[k]] += 1
		k = k // df[k]
	return m
t = int(input())
while t:
	(s, g) = map(int, input().split())
	for i in range(g):
		(v, b) = list(map(int, input().split()))
		v = check2(v)
		b = check2(b)
		d = set(list(v.keys()) + list(b.keys()))
		for i in d:
			h = min(v[i], b[i])
			v[i] -= h
			b[i] -= h
		bhu = 0
		for i in d:
			bhu += i * (v[i] + b[i])
		print(bhu)
	t -= 1


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def j1():
	j2 = 100001
	j3 = [0 for i in range(j2)]
	j3[1] = 1
	for j4 in range(2, j2):
		j3[j4] = j4
	for j5 in range(4, j2, 2):
		j3[j5] = 2
	for j6 in range(3, math.ceil(math.sqrt(j2))):
		if j3[j6] == j6:
			for j in range(j6 * j6, j2, j6):
				if j3[j] == j:
					j3[j] = j6
	return j3
j3 = j1()

def j7(x):
	j8 = defaultdict(lambda : 0)
	while x != 1:
		j8[j3[x]] += 1
		x = x // j3[x]
	return j8

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(j9, j10) = list(map(int, input().split()))
		j9 = j7(j9)
		j10 = j7(j10)
		x = set(list(j9.keys()) + list(j10.keys()))
		for i in x:
			y = min(j9[i], j10[i])
			j9[i] -= y
			j10[i] -= y
		ans = 0
		for i in x:
			ans += i * (j9[i] + j10[i])
		print(ans)
j11 = 1
j11 = int(input())
for _ in range(j11):
	solve()


import sys
import math
from collections import defaultdict

def myprime():
	MAXN = 100001
	prime = [0 for i in range(MAXN)]
	prime[1] = 1
	for i in range(2, MAXN):
		prime[i] = i
	for i in range(4, MAXN, 2):
		prime[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if prime[i] == i:
			for j in range(i * i, MAXN, i):
				if prime[j] == j:
					prime[j] = i
	return prime
prime = myprime()

def getPrimefactor(x):
	rr = defaultdict(lambda : 0)
	while x != 1:
		rr[prime[x]] += 1
		x = x // prime[x]
	return rr

def solve():
	(n, q) = list(map(int, sys.stdin.readline().split()))
	for i in range(q):
		(u, v) = list(map(int, sys.stdin.readline().split()))
		u = getPrimefactor(u)
		v = getPrimefactor(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			temp = min(u[i], v[i])
			u[i] -= temp
			v[i] -= temp
		finalans = 0
		for i in x:
			finalans += i * (u[i] + v[i])
		print(finalans)
t = 1
t = int(sys.stdin.readline())
for _ in range(t):
	solve()


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = sieveForSmallestPrimeFactor()

def getPrimeFactorizationLOGN(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = getPrimeFactorizationLOGN(u)
		v = getPrimeFactorizationLOGN(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)
t = 1
t = int(input())
for _ in range(t):
	solve()


import sys
import bisect, string, math, time, functools, random, fractions
from bisect import *
from heapq import heappush, heappop, heapify
from queue import PriorityQueue
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
import random
import queue

def smallestfactor():
	mx = 100001
	sm = [0 for i in range(mx)]
	sm[1] = 1
	for i in range(2, mx):
		sm[i] = i
	for i in range(4, mx, 2):
		sm[i] = 2
	for i in range(3, math.ceil(math.sqrt(mx))):
		if sm[i] == i:
			for j in range(i * i, mx, i):
				if sm[j] == j:
					sm[j] = i
	return sm
sm = smallestfactor()

def solve(x):
	res = defaultdict(lambda : 0)
	while x != 1:
		res[sm[x]] += 1
		x = x // sm[x]
	return res
t = int(input())
while t:
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		u = solve(u)
		v = solve(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		res = 0
		for i in x:
			res += (u[i] + v[i]) * i
		print(res)
	t -= 1


import math
from collections import defaultdict

def function1():
	maximum_of_all = 1000001
	temp = [0 for j in range(maximum_of_all)]
	temp[1] = 1000001
	for j in range(2, maximum_of_all):
		temp[j] = j
	for j in range(4, maximum_of_all, 2):
		temp[j] = 2
	for j in range(3, math.ceil(math.sqrt(maximum_of_all))):
		if temp[j] == j:
			for i in range(j * j, maximum_of_all, j):
				if temp[i] == i:
					temp[i] = j
	return temp
temp = function1()

def function2(var):
	result = defaultdict(lambda : 0)
	while var != 1:
		result[temp[var]] += 1
		var = var // temp[var]
	return result

def pushkar():
	(num, qry) = list(map(int, input().split()))
	for j in range(qry):
		(m, n) = list(map(int, input().split()))
		m = function2(m)
		n = function2(n)
		raj = set(list(m.keys()) + list(n.keys()))
		for i in raj:
			k = min(m[i], n[i])
			m[i] -= k
			n[i] -= k
		answer = 0
		for j in raj:
			answer += j * (m[j] + n[j])
		print(answer)
tc = 1
tc = int(input())
for j in range(tc):
	pushkar()


import math
from collections import defaultdict
mylimit = 100009

def AnotherHelpingFunction():
	finalVariable = [0 for i in range(mylimit)]
	finalVariable[1] = 1
	for i in range(2, mylimit):
		finalVariable[i] = i
	for i in range(4, mylimit, 2):
		finalVariable[i] = 2
	for i in range(3, math.ceil(math.sqrt(mylimit))):
		if finalVariable[i] == i:
			for j in range(i * i, mylimit, i):
				if finalVariable[j] == j:
					finalVariable[j] = i
	return finalVariable
gettingValue = AnotherHelpingFunction()

def FindTrueValue(asish):
	ReturnedVal = defaultdict(int)
	while asish != 1:
		ReturnedVal[gettingValue[asish]] += 1
		asish //= gettingValue[asish]
	return ReturnedVal
trials = int(input())
while trials:
	trials -= 1
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(presence, haveToGo) = list(map(int, input().split()))
		haveToGo = FindTrueValue(haveToGo)
		presence = FindTrueValue(presence)
		GettingAllElementInSet = set([*presence.keys(), *haveToGo.keys()])
		for i in GettingAllElementInSet:
			FindingSecondValue = min(presence[i], haveToGo[i])
			presence[i] -= FindingSecondValue
			haveToGo[i] -= FindingSecondValue
		FinalAns = 0
		for i in GettingAllElementInSet:
			FinalAns += i * (presence[i] + haveToGo[i])
		print(FinalAns)


import sys
import math
from collections import defaultdict

def sieve():
	MAXN = 100000
	spfst = [0 for i in range(MAXN)]
	spfst[1] = 100000
	for i in range(2, MAXN):
		spfst[i] = i
	for i in range(4, MAXN, 2):
		spfst[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spfst[i] == i:
			for j in range(i * i, MAXN, i):
				if spfst[j] == j:
					spfst[j] = i
	return spfst
spfst = sieve()

def prime(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spfst[x]] += 1
		x = x // spfst[x]
	return ret

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = prime(u)
		v = prime(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		result = 0
		for i in x:
			result += i * (u[i] + v[i])
		print(result)
test = 1
test = int(input())
for _ in range(test):
	solve()


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sSP():
	MN = 100001
	spf = [0 for i in range(MN)]
	spf[1] = 1
	for i in range(2, MN):
		spf[i] = i
	for i in range(4, MN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MN))):
		if spf[i] == i:
			for j in range(i * i, MN, i):
				if spf[j] == j:
					spf[j] = i
	return spf
sf = sSP()

def pf(i):
	ref = defaultdict(lambda : 0)
	while i != 1:
		ref[sf[i]] += 1
		i = i // sf[i]
	return ref
t = 1
t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = pf(u)
		v = pf(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			z = min(u[i], v[i])
			u[i] -= z
			v[i] -= z
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)


from collections import defaultdict
import math
import sys

def primeFact(x):
	check = 0
	flag = True
	Bool = 1
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		check += 2
		x = x // spf[x]
	Bool = 0
	return ret

def sieve():
	Bool = True
	maximize = 100001
	maxN = 100001
	spf = [0 for i in range(maxN)]
	spf[1] = 1
	pick = 3
	for i in range(2, maxN):
		maximize -= 1
		spf[i] = i
		pick += 3
	for i in range(4, maxN, 2):
		spf[i] = 2
		maximize -= 1
	for i in range(3, math.ceil(math.sqrt(maxN))):
		if spf[i] == i:
			Bool = False
			for j in range(i * i, maxN, i):
				maximize -= 1
				if spf[j] == j:
					Bool = True
					pick += 1
					spf[j] = i
	pick += maximize
	Bool = False
	return spf
spf = sieve()
checker = 100001
T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	sums = 0
	for z in range(Q):
		(u, v) = map(int, input().split())
		v = primeFact(v)
		u = primeFact(u)
		sums = 1
		cnt = 0
		x = set(list(u.keys()) + list(v.keys()))
		values = '12345'
		marker = 1
		for i in x:
			marker += 1
			y = min(u[i], v[i])
			sums += 1
			cnt += marker + sums
			v[i] -= y
			u[i] -= y
		ans = 0
		for i in x:
			sums += 9
			ans += i * (u[i] + v[i])
		print(str(ans))


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sieveForPF():
	MAX = 100001
	spf = [0 for i in range(MAX)]
	spf[1] = 1
	for i in range(2, MAX):
		spf[i] = i
	for i in range(4, MAX, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAX))):
		if spf[i] == i:
			for j in range(i * i, MAX, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = sieveForPF()

def getPF(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = getPF(u)
		v = getPF(v)
		X = set(list(u.keys()) + list(v.keys()))
		for i in X:
			yy = min(u[i], v[i])
			u[i] -= yy
			v[i] -= yy
		ans = 0
		for i in X:
			ans += i * (u[i] + v[i])
		print(ans)
t = 1
t = int(input())
for _ in range(t):
	solve()


import sys
import math
from collections import defaultdict
S = sys.stdin.readline

def helper():
	M = 100001
	spf = [0] * M
	spf[1] = 1
	for i in range(2, M):
		spf[i] = i
	for i in range(4, M, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(M))):
		if spf[i] == i:
			for j in range(i ** 2, M, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = helper()

def helper1(x):
	r = defaultdict(lambda : 0)
	while x != 1:
		r[spf[x]] += 1
		x = x // spf[x]
	return r
test = int(input())
while test:
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		u = helper1(u)
		v = helper1(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		out = 0
		for i in x:
			out += i * (u[i] + v[i])
		print(out)
	test -= 1


import math
t = int(input())
from collections import Counter
import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
sieve()

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		ans = 0
		if y > x:
			(x, y) = (y, x)
		if x == y:
			print(0)
			continue
		else:
			g = mt.gcd(x, y)
			a = x // g
			count = getFactorization(a)
			c = Counter(count)
			for (key, value) in c.items():
				ans += key * value
			b = y // g
			count = getFactorization(b)
			d = Counter(count)
			for (key, value) in d.items():
				ans += key * value
			print(ans)


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sfspf():
	maxm = 100001
	main_data_for_the_result = [0 for i in range(maxm)]
	main_data_for_the_result[1] = 1
	for i in range(2, maxm):
		main_data_for_the_result[i] = i
	for i in range(4, maxm, 2):
		main_data_for_the_result[i] = 2
	for i in range(3, math.ceil(math.sqrt(maxm))):
		if main_data_for_the_result[i] == i:
			for j in range(i * i, maxm, i):
				if main_data_for_the_result[j] == j:
					main_data_for_the_result[j] = i
	return main_data_for_the_result
main_data_for_the_result = sfspf()

def gettheprimefectrozationofthenumber(x):
	res = defaultdict(lambda : 0)
	while x != 1:
		res[main_data_for_the_result[x]] += 1
		x = x // main_data_for_the_result[x]
	return res

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = gettheprimefectrozationofthenumber(u)
		v = gettheprimefectrozationofthenumber(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)
t = 1
t = int(input())
for _ in range(t):
	solve()


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def shubham():
	maxValue = 100001
	arr = [0 for i in range(maxValue)]
	arr[1] = 1
	for i in range(2, maxValue):
		arr[i] = i
	for i in range(4, maxValue, 2):
		arr[i] = 2
	for i in range(3, math.ceil(math.sqrt(maxValue))):
		if arr[i] == i:
			for j in range(i * i, maxValue, i):
				if arr[j] == j:
					arr[j] = i
	return arr
arr = shubham()

def bansal(temp):
	x = defaultdict(lambda : 0)
	while temp != 1:
		x[arr[temp]] += 1
		temp = temp // arr[temp]
	return x

def google():
	(N, Q) = list(map(int, input().split()))
	for i in range(Q):
		(u, v) = list(map(int, input().split()))
		u = bansal(u)
		v = bansal(v)
		z = set(list(u.keys()) + list(v.keys()))
		for i in z:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in z:
			ans += i * (u[i] + v[i])
		print(ans)
t = 1
t = int(input())
for _ in range(t):
	google()


import math
t = int(input())
for T in range(t):
	(n, q) = map(int, input().split())
	for i in range(q):
		(a, b) = map(int, input().split())
		g = math.gcd(a, b)
		a = a // g
		b = b // g
		ans = 0
		while a % 2 == 0:
			ans += 2
			a //= 2
		while b % 2 == 0:
			ans += 2
			b //= 2
		j = 3
		while a > 1 and j <= math.sqrt(a):
			while a % j == 0:
				ans += j
				a //= j
			j += 2
		j = 3
		while b > 1 and j <= math.sqrt(b):
			while b % j == 0:
				ans += j
				b //= j
			j += 2
		if a > 1:
			ans += a
			a = 1
		if b > 1:
			ans += b
			b = 1
		print(ans)


from ctypes import cdll
from email.policy import default
from operator import itemgetter
from sys import maxsize, stdin
from collections import Counter, defaultdict
import numpy as np
from math import ceil, sqrt

def soe() -> list:
	maximum = 100001
	temp2 = list((0 for i in range(maximum)))
	temp2[1] = 1
	for i in range(2, maximum):
		temp2[i] = i
	for i in range(4, maximum, 2):
		temp2[i] = 2
	for i in range(3, ceil(sqrt(maximum))):
		if temp2[i] == i:
			for j in range(i * i, maximum, i):
				if temp2[j] == j:
					temp2[j] = i
	return temp2
temp2 = soe()

def pf(val: int) -> defaultdict:
	temp = defaultdict(lambda : 0)
	while val != 1:
		temp[temp2[val]] += 1
		val //= temp2[val]
	return temp
t = int(stdin.readline().strip())
while t > 0:
	(n, q) = map(int, stdin.readline().strip().split(' '))
	for i in range(q):
		(u, v) = map(int, stdin.readline().strip().split(' '))
		u = pf(val=u)
		v = pf(val=v)
		res1 = u.keys()
		res2 = v.keys()
		res1 = list(res1)
		res2 = list(res2)
		check = set(res1 + res2)
		for i in check:
			m = min(u[i], v[i])
			u[i] -= m
			v[i] -= m
		ans = 0
		for i in check:
			ans += i * (u[i] + v[i])
		print(ans)
	t -= 1


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def get_prime_numbers_quickly():
	MAX_INT_VALUE = 100001
	get_prime_in_constant = [0 for index_value in range(MAX_INT_VALUE)]
	get_prime_in_constant[1] = 1
	for index_value in range(2, MAX_INT_VALUE):
		get_prime_in_constant[index_value] = index_value
	for index_value in range(4, MAX_INT_VALUE, 2):
		get_prime_in_constant[index_value] = 2
	for index_value in range(3, math.ceil(math.sqrt(MAX_INT_VALUE))):
		if get_prime_in_constant[index_value] == index_value:
			for j in range(index_value * index_value, MAX_INT_VALUE, index_value):
				if get_prime_in_constant[j] == j:
					get_prime_in_constant[j] = index_value
	return get_prime_in_constant
get_prime_in_constant = get_prime_numbers_quickly()

def primeFactorsFunction(input_number):
	list_of_prime_factors = defaultdict(lambda : 0)
	while input_number != 1:
		list_of_prime_factors[get_prime_in_constant[input_number]] += 1
		input_number = input_number // get_prime_in_constant[input_number]
	return list_of_prime_factors

def answer_finding_method():
	(n, q) = list(map(int, input().split()))
	for index_value in range(q):
		(u, v) = list(map(int, input().split()))
		u = primeFactorsFunction(u)
		v = primeFactorsFunction(v)
		x = set(list(u.keys()) + list(v.keys()))
		for index_value in x:
			y = min(u[index_value], v[index_value])
			u[index_value] = u[index_value] - y
			v[index_value] = v[index_value] - y
		answer = 0
		for index_value in x:
			answer += index_value * (u[index_value] + v[index_value])
		print(answer)
testcases_for_given_problem = 1
testcases_for_given_problem = int(input())
while testcases_for_given_problem:
	testcases_for_given_problem -= 1
	answer_finding_method()


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	primes = []
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(2, n + 1):
		if prime[i] == True:
			primes.append(i)
	return (primes, prime)

def primeFactors(n, current, prim, bools):
	ans = 0
	k = n
	c = 0
	while n > 1 and current[n] == 0:
		if bools[n]:
			ans += n
			n = 1
		if n % prim[c] == 0:
			ans += prim[c]
			n = n // prim[c]
		else:
			c = c + 1
	current[k] = ans + current[n]
import math
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	current = [0 for i in range(n + 1)]
	(prims, bools) = SieveOfEratosthenes(n)
	for i in range(2, n + 1):
		primeFactors(i, current, prims, bools)
	for i in range(q):
		(a, b) = map(int, input().split())
		x = math.gcd(a, b)
		if x == a and x == b:
			print(0)
		elif x == a:
			print(current[b // x])
		elif x == b:
			print(current[a // x])
		else:
			print(current[a // x] + current[b // x])


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sieveForSmallestPrimeFactor():
	M = 109001
	spf = [0 for i in range(M)]
	spf[1] = 1
	for i in range(2, M):
		spf[i] = i
	for i in range(4, M, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(M))):
		if spf[i] == i:
			for j in range(i * i, M, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = sieveForSmallestPrimeFactor()

def LOGN(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = LOGN(u)
		v = LOGN(v)
		x = set(list(u.keys()) + list(v.keys()))
		for k in x:
			y = min(u[k], v[k])
			u[k] -= y
			v[k] -= y
		ans = 0
		for j in x:
			ans += j * (u[j] + v[j])
		print(ans)
w = 1
w = int(input())
for _ in range(w):
	solve()


import math
primes = []
lcd = {}
Range = 200001
isPrime = [True for x in range(Range)]
temp = 2
for i in range(temp):
	isPrime[i] = False
for i in range(2, int(math.sqrt(Range))):
	if isPrime[i]:
		for j in range(i * i, Range, i):
			isPrime[j] = False
			if j not in lcd:
				lcd[j] = i
for i in range(Range):
	if isPrime[i]:
		primes.append(i)

def primeSum(n):
	if n <= 1:
		return 0
	ans = 0
	while n in lcd:
		ans += lcd[n]
		n //= lcd[n]
	return ans + n
t = int(input())
while t > 0:
	t -= 1
	(n, q) = [int(x) for x in input().split()]
	for i in range(q):
		(u, v) = [int(x) for x in input().split()]
		gcd = math.gcd(u, v)
		ans = primeSum(u // gcd) + primeSum(v // gcd)
		print(ans)


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def fun():
	P = 100001
	pp = [0 for ps in range(P)]
	pp[1] = 1
	for ps in range(2, P):
		pp[ps] = ps
	for ps in range(4, P, 2):
		pp[ps] = 2
	for ps in range(3, math.ceil(math.sqrt(P))):
		if pp[ps] == ps:
			for j in range(ps * ps, P, ps):
				if pp[j] == j:
					pp[j] = ps
	return pp
pp = fun()

def myFunc2(xs):
	res = defaultdict(lambda : 0)
	while xs != 1:
		res[pp[xs]] += 1
		xs = xs // pp[xs]
	return res

def myFunc():
	(ns, qs) = list(map(int, input().split()))
	for ps in range(qs):
		(us, vs) = list(map(int, input().split()))
		us = myFunc2(us)
		vs = myFunc2(vs)
		xs = set(list(us.keys()) + list(vs.keys()))
		for ps in xs:
			ys = min(us[ps], vs[ps])
			us[ps] -= ys
			vs[ps] -= ys
		ans = 0
		for ps in xs:
			ans += ps * (us[ps] + vs[ps])
		print(ans)

def main():
	ts = 1
	ts = int(input())
	for _ in range(ts):
		myFunc()
main()


import math
from collections import defaultdict
LIMITN = 100007

def sieve():
	spf = [0 for i in range(LIMITN)]
	spf[1] = 1
	for i in range(2, LIMITN):
		spf[i] = i
	for i in range(4, LIMITN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(LIMITN))):
		if spf[i] == i:
			for j in range(i * i, LIMITN, i):
				if spf[j] == j:
					spf[j] = i
	return spf
sf = sieve()

def get(xxx):
	d = defaultdict(int)
	while xxx != 1:
		d[sf[xxx]] += 1
		xxx //= sf[xxx]
	return d
t = int(input())
while t:
	t -= 1
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(src, dest) = list(map(int, input().split()))
		src = get(src)
		dest = get(dest)
		xxx = set([*src.keys(), *dest.keys()])
		for i in xxx:
			yyy = min(src[i], dest[i])
			src[i] -= yyy
			dest[i] -= yyy
		res = 0
		for i in xxx:
			res += i * (src[i] + dest[i])
		print(res)


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sievef():
	MAXN = 100001
	num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	for i in range(2, MAXN):
		spf[i] = i
		num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	for i in range(4, MAXN, 2):
		spf[i] = 2
		num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = sievef()

def getp(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def solve():
	(n, q) = list(map(int, input().split()))
	num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	num = 1234
	reversed_num = 0
	while num != 0:
		digit = num % 10
		reversed_num = reversed_num * 10 + digit
		num //= 10
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = getp(u)
		v = getp(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)
t = 1
t = int(input())
for _ in range(t):
	solve()


import sys, math
from collections import defaultdict
input = sys.stdin.readline

def pp(c):
	f = defaultdict(lambda : 0)
	while c != 1:
		f[p[c]] = f[p[c]] + 1
		c = c // p[c]
	return f

def s1():
	m = 100001
	p = [0 for i in range(m)]
	p[1] = 1
	for i in range(2, m):
		p[i] = i
	for i in range(4, m, 2):
		p[i] = 2
	for i in range(3, math.ceil(math.sqrt(m))):
		if p[i] == i:
			for k in range(i * i, m, i):
				if p[k] == k:
					p[k] = i
	return p
p = s1()

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		v = pp(v)
		u = pp(u)
		y = set(list(u.keys()) + list(v.keys()))
		for i in y:
			if u[i] < v[i]:
				x = u[i]
			else:
				x = v[i]
			v[i] -= x
			u[i] -= x
		ans = 0
		for i in y:
			ans += i * (u[i] + v[i])
		print(ans)
test = 1
test = int(input())
for _ in range(test):
	solve()


import sys
import math
from collections import defaultdict

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = sieveForSmallestPrimeFactor()

def getPrimeFactorizationLogn(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret
t = int(input())
while t > 0:
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = getPrimeFactorizationLogn(u)
		v = getPrimeFactorizationLogn(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		res = 0
		for i in x:
			res += i * (u[i] + v[i])
		print(res)
	t -= 1


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def primefactor():
	max_n = 100001
	pf = [0 for j in range(max_n)]
	pf[1] = 1
	for i in range(2, max_n):
		pf[i] = i
	for i in range(4, max_n, 2):
		pf[i] = 2
	for i in range(3, math.ceil(math.sqrt(max_n))):
		if pf[i] == i:
			for k in range(i * i, max_n, i):
				if pf[k] == k:
					pf[k] = i
	return pf
pf = primefactor()

def fact(a):
	res = defaultdict(lambda : 0)
	while a != 1:
		res[pf[a]] += 1
		a = a // pf[a]
	return res

def fin():
	(n, q) = list(map(int, input().split(' ')))
	for i in range(q):
		(u, v) = list(map(int, input().split(' ')))
		u = fact(u)
		v = fact(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)
t = int(input())
for _ in range(t):
	fin()


from math import floor
mxV = 10 ** 5 + 1
mxP = floor(mxV ** 0.5) + 3
p_factors = [[] for i in range(mxV)]

def pre_compute():
	for i in range(2, mxP):
		if len(p_factors[i]) > 0:
			continue
		for j in range(i, mxV, i):
			p_factors[j].append([i, 0])
	for i in range(2, mxV):
		v = i
		for pf in p_factors[i]:
			p = pf[0]
			count = 0
			while v % p == 0:
				count += 1
				v //= p
			pf[1] = count
		if v > 1:
			p_factors[i].append([v, 1])
pre_compute()
for t in range(int(input())):
	(n, q) = tuple(map(int, input().strip().split()))
	for x in range(q):
		(u, v) = tuple(map(int, input().strip().split()))
		ans = 0
		u_pf = p_factors[u]
		v_pf = p_factors[v]
		(i, u_size) = (0, len(u_pf))
		(j, v_size) = (0, len(v_pf))
		while i < u_size and j < v_size:
			(pu, pv) = (u_pf[i][0], v_pf[j][0])
			(puc, pvc) = (u_pf[i][1], v_pf[j][1])
			if pu == pv:
				ans += pu * abs(puc - pvc)
				i += 1
				j += 1
			elif pu < pv:
				ans += pu * puc
				i += 1
			else:
				ans += pv * pvc
				j += 1
		while i < u_size:
			ans += u_pf[i][0] * u_pf[i][1]
			i += 1
		while j < v_size:
			ans += v_pf[j][0] * v_pf[j][1]
			j += 1
		print(ans)


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sfspf():
	MAXN = 100001
	sp = [0 for i in range(MAXN)]
	sp[1] = 1
	for i in range(2, MAXN):
		sp[i] = i
	for i in range(4, MAXN, 2):
		sp[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if sp[i] == i:
			for j in range(i * i, MAXN, i):
				if sp[j] == j:
					sp[j] = i
	return sp
sp = sfspf()

def gpfl(x):
	re = defaultdict(lambda : 0)
	while x != 1:
		re[sp[x]] += 1
		x = x // sp[x]
	return re

def sol():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = gpfl(u)
		v = gpfl(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		an = 0
		for i in x:
			an += i * (u[i] + v[i])
		print(an)
for _ in range(int(input())):
	sol()


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def s1():
	MAX = 100001
	s = [0 for i in range(MAX)]
	s[1] = 1
	for i in range(2, MAX):
		s[i] = i
	for i in range(4, MAX, 2):
		s[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAX))):
		if s[i] == i:
			for j in range(i * i, MAX, i):
				if s[j] == j:
					s[j] = i
	return s
s = s1()

def gp(n):
	res = defaultdict(lambda : 0)
	while n != 1:
		res[s[n]] += 1
		n = n // s[n]
	return res

def solve():
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = gp(u)
		v = gp(v)
		ans = set(list(u.keys()) + list(v.keys()))
		for i in ans:
			m = min(u[i], v[i])
			u[i] -= m
			v[i] -= m
		a = 0
		for i in ans:
			a += i * (u[i] + v[i])
		print(a)
t = 1
t = int(input())
for _ in range(t):
	solve()


import math as mm
import sys as ss
from collections import defaultdict as dd

def help1():
	MN = 100001
	res = [0 for i in range(MN)]
	res[1] = 1
	for _ in range(2, MN):
		res[_] = _
	for j in range(4, MN, 2):
		res[j] = 2
	for i in range(3, mm.ceil(mm.sqrt(MN))):
		if res[i] == i:
			for k in range(i * i, MN, i):
				if res[k] == k:
					res[k] = i
	return res
res = help1()

def help2(a):
	ans = dd(lambda : 0)
	while a != 1:
		ans[res[a]] += 1
		a = a // res[a]
	return ans
input = ss.stdin.readline

def solve_this_case():
	(n, x) = map(int, input().split())
	for z in range(1, x + 1):
		(a, b) = map(int, input().split())
		b = help2(b)
		a = help2(a)
		q = set(list(a.keys()) + list(b.keys()))
		for j in q:
			y = min(a[j], b[j])
			a[j] = a[j] - y
			b[j] = b[j] - y
		res = 0
		for k in q:
			res += k * (a[k] + b[k])
		print(res)

def main():
	t = int(input())
	for __ in range(t):
		solve_this_case()
main()


import math

def findMinSum(num):
	sum = 0
	i = 2
	while i * i <= num:
		while num % i == 0:
			sum += i
			num //= i
		i += 1
	if num == 1:
		return sum
	sum += num
	return sum
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for qq in range(q):
		(u, v) = map(int, input().split())
		(u, v) = (min(u, v), max(u, v))
		if u == v:
			print(0)
		elif v % u == 0:
			print(findMinSum(v // u))
		else:
			g = math.gcd(u, v)
			print(findMinSum(u // g) + findMinSum(v // g))


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sx():
	mxn = 100001
	s = [0 for i in range(mxn)]
	s[1] = 1
	for i in range(2, mxn):
		s[i] = i
	for i in range(4, mxn, 2):
		s[i] = 2
	for i in range(3, math.ceil(math.sqrt(mxn))):
		if s[i] == i:
			for j in range(i * i, mxn, i):
				if s[j] == j:
					s[j] = i
	return s
s = sx()

def f(x):
	res = defaultdict(lambda : 0)
	while x != 1:
		res[s[x]] += 1
		x = x // s[x]
	return res

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(a, b) = list(map(int, input().split()))
		a = f(a)
		b = f(b)
		x = set(list(a.keys()) + list(b.keys()))
		for i in x:
			y = min(a[i], b[i])
			a[i] -= y
			b[i] -= y
		ans = 0
		for i in x:
			ans += i * (a[i] + b[i])
		print(ans)
t = 1
t = int(input())
for j in range(t):
	solve()


import sys
import math
from collections import defaultdict

def smallprimefactor():
	maxn = 100001
	spf = [0 for i in range(maxn)]
	spf[1] = 1
	for i in range(2, maxn):
		spf[i] = i
	for i in range(4, maxn, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(maxn))):
		if spf[i] == i:
			for j in range(i * i, maxn, i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = smallprimefactor()

def getprimefactor(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def solve():
	(n, q) = list(map(int, input().split()))
	for i in range(q):
		(u, v) = list(map(int, input().split()))
		u = getprimefactor(u)
		v = getprimefactor(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sieve():
	mymxy = 100001
	ggspfis = [0 for i in range(mymxy)]
	ggspfis[1] = 1
	for i in range(2, mymxy):
		ggspfis[i] = i
	for i in range(4, mymxy, 2):
		ggspfis[i] = 2
	for i in range(3, math.ceil(math.sqrt(mymxy))):
		if ggspfis[i] == i:
			for j in range(i * i, mymxy, i):
				if ggspfis[j] == j:
					ggspfis[j] = i
	return ggspfis
ggspfis = sieve()

def getp(x):
	ret = defaultdict(lambda : 0)
	while x != 1:
		ret[ggspfis[x]] += 1
		x = x // ggspfis[x]
	return ret

def solve():
	(mynn, letsq) = list(map(int, input().split()))
	for i in range(letsq):
		(gguu, v) = list(map(int, input().split()))
		gguu = getp(gguu)
		v = getp(v)
		x = set(list(gguu.keys()) + list(v.keys()))
		for i in x:
			y = min(gguu[i], v[i])
			gguu[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (gguu[i] + v[i])
		print(ans)
t = 1
t = int(input())
for _ in range(t):
	solve()


import math
N = int(100000.0)
sieve = [True] * (N + 1)
factor = [0] * (N + 1)
for j in range(2, N + 1):
	if sieve[j]:
		factor[j] = j
		for k in range(2 * j, N + 1, j):
			factor[k] = j
			sieve[k] = False
sm = [0] * (N + 1)
for j in range(2, N + 1):
	sm[j] = factor[j] + sm[j // factor[j]]
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	for _ in range(q):
		(u, v) = map(int, input().split())
		l = math.gcd(u, v)
		print(sm[u] - sm[l] + sm[v] - sm[l])


import math

def printDivisors(n):
	v = []
	while n % 2 == 0:
		v.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			v.append(i)
			n = n // i
	if n > 2:
		v.append(n)
	return v
import collections
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(x, y) = map(int, input().split())
		div_x = printDivisors(x)
		div_y = printDivisors(y)
		d = collections.defaultdict(lambda : 0)
		for j in div_x:
			d[j] += 1
		for j in div_y:
			d[j] -= 1
		ans = 0
		for j in d:
			ans += abs(d[j]) * j
		print(ans)


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def smpf():
	MAXN = 100001
	some = [0 for i in range(MAXN)]
	some[1] = 1
	for i in range(2, MAXN):
		some[i] = i
	for i in range(4, MAXN, 2):
		some[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if some[i] == i:
			for j in range(i * i, MAXN, i):
				if some[j] == j:
					some[j] = i
	return some
some = smpf()

def gpfln(shi):
	result = defaultdict(lambda : 0)
	while shi != 1:
		result[some[shi]] += 1
		shi = shi // some[shi]
	return result

def shiva_solution():
	(n, ran) = list(map(int, input().split()))
	for i in range(ran):
		(sk, ga) = list(map(int, input().split()))
		sk = gpfln(sk)
		ga = gpfln(ga)
		shi = set(list(sk.keys()) + list(ga.keys()))
		for i in shi:
			va = min(sk[i], ga[i])
			sk[i] -= va
			ga[i] -= va
		answer = 0
		for i in shi:
			answer += i * (sk[i] + ga[i])
		print(answer)
test = int(input())
for _ in range(test):
	shiva_solution()


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def sfsp():
	maxii = 100001
	pdf = [0 for h in range(maxii)]
	pdf[1] = 1
	for h in range(2, maxii):
		pdf[h] = h
	for h in range(4, maxii, 2):
		pdf[h] = 2
	for h in range(3, math.ceil(math.sqrt(maxii))):
		if pdf[h] == h:
			for j in range(h * h, maxii, h):
				if pdf[j] == j:
					pdf[j] = h
	return pdf
pdf = sfsp()

def gpfl(m):
	ret = defaultdict(lambda : 0)
	while m != 1:
		ret[pdf[m]] += 1
		m = m // pdf[m]
	return ret

def resans():
	(n, r) = list(map(int, input().split()))
	for h in range(r):
		(s, t) = list(map(int, input().split()))
		s = gpfl(s)
		t = gpfl(t)
		m = set(list(s.keys()) + list(t.keys()))
		for h in m:
			y = min(s[h], t[h])
			s[h] -= y
			t[h] -= y
		sol = 0
		for h in m:
			sol += h * (s[h] + t[h])
		print(sol)
t = 1
t = int(input())
for _ in range(t):
	resans()


from math import gcd

def maxfact(n):
	i = 2
	ans = 0
	while i * i <= n:
		while n % i == 0:
			ans += i
			n = n // i
		i += 1
	if n != 1:
		return ans + n
	return ans
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for ii in range(q):
		(u, v) = map(int, input().split())
		x = gcd(u, v)
		ans = maxfact(u) + maxfact(v) - 2 * maxfact(x)
		print(ans)


import sys
import math
from collections import defaultdict

def baba():
	maxi = 10 ** 6
	lauda = [0 for i in range(maxi)]
	lauda[1] = 1
	for i in range(2, maxi):
		lauda[i] = i
	for i in range(4, maxi, 2):
		lauda[i] = 2
	for i in range(3, math.ceil(math.sqrt(maxi))):
		if lauda[i] == i:
			for j in range(i * i, maxi, i):
				if lauda[j] == j:
					lauda[j] = i
	return lauda
lauda = baba()

def maa(x):
	rate = defaultdict(lambda : 0)
	while x != 1:
		rate[lauda[x]] += 1
		x = x // lauda[x]
	return rate

def solve():
	if 5 == 8:
		print('')
	if 5 == 8:
		print('')
	if 5 == 8:
		print('')
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		u = maa(u)
		v = maa(v)
		x = set(list(u.keys()) + list(v.keys()))
		for i in x:
			y = min(u[i], v[i])
			u[i] -= y
			v[i] -= y
		ans = 0
		for i in x:
			ans += i * (u[i] + v[i])
		print(ans)
t = int(input())
for i in range(t):
	if 5 == 8:
		print('')
	hui = 0
	while hui < 2:
		hui += 1
	solve()


def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)

def factorize(n):
	sieve = [True] * int(n ** 0.5 + 2)
	for x in range(2, int(len(sieve) ** 0.5 + 2)):
		if not sieve[x]:
			continue
		for i in range(x * x, len(sieve), x):
			sieve[i] = False
	factors = []
	for i in range(2, len(sieve)):
		if i * i > n:
			break
		if not sieve[i]:
			continue
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 1:
		factors.append(n)
	return sum(factors)
T = int(input())
for ts in range(T):
	(N, Q) = map(int, input().split(' '))
	for q in range(Q):
		(u, v) = map(int, input().split(' '))
		if u == v:
			print(0)
		else:
			A = computeGCD(u, v)
			print(factorize(u // A) + factorize(v // A))


import math
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	for i in range(q):
		(a, b) = map(int, input().split())
		if a == b:
			print(0)
			continue
		(a, b) = (min(a, b), max(a, b))
		g = math.gcd(a, b)
		(a, b) = (a // g, b // g)
		suma = 0
		i = 2
		while i * i <= a + 2:
			while a % i == 0:
				suma += i
				a //= i
			i += 1
		if a != 1:
			suma += a
		sumb = 0
		i = 2
		while i * i <= b + 2:
			while b % i == 0:
				sumb += i
				b //= i
			i += 1
		if b != 1:
			suma += b
		print(suma + sumb)


import math
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		num = math.gcd(u, v)
		ans = 0
		u = u // num
		while u != 1:
			while u % 2 == 0:
				ans += 2
				u = u // 2
			for j in range(3, int(u ** 0.5) + 1, 2):
				while u % j == 0:
					ans += j
					u = u // j
			if u > 2:
				ans += u
				break
		u = v
		u = u // num
		while u != 1:
			while u % 2 == 0:
				ans += 2
				u = u // 2
			for j in range(3, int(u ** 0.5) + 1, 2):
				while u % j == 0:
					ans += j
					u = u // j
			if u > 2:
				ans += u
				break
		print(ans)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

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

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

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def main():
	try:
		(n, q) = In()
		for i in range(q):
			(a, b) = In()
			(a1, b1, c1) = (getFactorization(a), getFactorization(b), getFactorization(math.gcd(a, b)))
			print(sum(a1) + sum(b1) - 2 * sum(c1))
	except:
		pass
M = 998244353
P = 1000000007
import math as mt
MAXN = 100001
global spf
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
sieve()
for _ in range(I()):
	main()


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def sieve():
	spf = [i for i in range(10 ** 5 + 10)]
	for i in range(2, len(spf), 2):
		spf[i] = 2
	for i in range(3, int(math.sqrt(len(spf))) + 1):
		if spf[i] == i:
			for j in range(i * i, len(spf), i):
				if spf[j] == j:
					spf[j] = i
	return spf
spf = sieve()

def factor(x):
	res = []
	while x != 1:
		res.append(spf[x])
		x //= spf[x]
	return res

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, q) = sep()
		for i in range(q):
			(u, v) = sep()
			if u > v:
				(u, v) = (v, u)
			p = math.gcd(u, v)
			u //= p
			factoru = sum(factor(u))
			v //= p
			factorv = sum(factor(v))
			print(factorv + factoru)
main()


from math import gcd
from math import sqrt

def PrimeFact(n):
	factors = {}
	for i in range(2, int(sqrt(n)) + 1):
		c = 0
		while n % i == 0:
			n //= i
			c += 1
			factors[i] = c
	if n > 1:
		factors[n] = 1
	return factors

def main():
	(n, q) = map(int, input().split())
	for i in range(q):
		(u, v) = map(int, input().split())
		if u == v:
			print(0)
		else:
			hcf = gcd(u, v)
			u = u // hcf
			v = v // hcf
			uf = PrimeFact(u)
			vf = PrimeFact(v)
			up = 0
			for (k, v) in uf.items():
				up += k * v
			vp = 0
			for (k, v) in vf.items():
				vp += k * v
			print(up + vp)
	return
for _ in range(int(input())):
	main()


import sys
from math import gcd, sqrt
input = lambda : sys.stdin.readline()
T = int(input())
for _ in range(T):
	(n, q) = map(int, input().strip().split())
	for t in range(q):
		(u, v) = map(int, input().strip().split())
		w = gcd(u, v)
		u = u // w
		v = v // w
		dic = {}
		while u % 2 == 0:
			dic[2] = dic.get(2, 0) + 1
			u //= 2
		for i in range(3, int(sqrt(u)) + 1, 2):
			while u % i == 0:
				dic[i] = dic.get(i, 0) + 1
				u //= i
		if u > 2:
			dic[u] = dic.get(u, 0) + 1
		while v % 2 == 0:
			dic[2] = dic.get(2, 0) + 1
			v //= 2
		for i in range(3, int(sqrt(v)) + 1, 2):
			while v % i == 0:
				dic[i] = dic.get(i, 0) + 1
				v //= i
		if v > 2:
			dic[v] = dic.get(v, 0) + 1
		L = 0
		for i in dic.keys():
			L += i * dic[i]
		print(L)


import sys, math
input = sys.stdin.readline
M = int(1000000000.0) + 7
N = int(100000.0) + 5
sieve = [1] * N
for i in range(2, N):
	if sieve[i] == 1:
		for j in range(i * i, N, i):
			sieve[j] = i
sumOfpf = [0] * N
for i in range(2, N):
	if sieve[i] == 1:
		sumOfpf[i] = i
	else:
		sumOfpf[i] = sieve[i] + sumOfpf[i // sieve[i]]

def solve():
	(n, q) = map(int, input().split())
	for _ in range(q):
		(u, v) = map(int, input().split())
		(u, v) = (min(u, v), max(u, v))
		if v % u == 0:
			print(sumOfpf[v // u])
		else:
			hcf = math.gcd(u, v)
			ans = sumOfpf[v // hcf] + sumOfpf[u // hcf]
			lcm = u * v // hcf
			if lcm // u <= n and lcm // v <= n:
				ans = min(ans, sumOfpf[lcm // u] + sumOfpf[lcm // v])
			print(ans)
for _ in range(int(input())):
	solve()