Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given an array A of size N. Initially, the array is filled with 0-s.

There are M types of operations that you can perform on array A. The i^{th} operation can be described by two integers (x_{i}, y_{i}). In this operation, you choose a set of indices S such that 

1 ≤ j ≤ N,
(j \bmod y_{i}) \neq 0,
A_{j} = 0, 

, then you set A_{j} = x_{i} for all j \in S.

You can perform the operations in any order, but one type of operation can't be done more than once. What is the maximum sum of integers of the array A you obtain if you perform the M operations optimally?

For example, consider the array A = [0, 0, 0, 0].
Suppose x = 3, y = 2. Here you can choose indices 1 and 3 and set A_{1} = A_{3} = 3. So the array A becomes [3, 0, 3, 0]. In this operation you can't choose the indices 2 and 4 because (2 \bmod 2) = 0, (4 \bmod 2) = 0. 
Suppose x = 5, y = 3 and you set A_{2} = 5. So the array A becomes [3, 5, 3, 0]. Here you can't choose index 1 because A_{1} > 0 and index 3 because (3 \bmod 3) = 0 and A_{3} > 0. However, you could also set A_{4} = 5.

Suppose x = 4, y = 4. Now you can't choose any index because A_{j} > 0  for all 1 ≤ j ≤ 3 and (4 \bmod 4) = 0. So the array remains same.

Note: Since input-output is large, prefer using fast input-output methods.

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

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each testcase contains M + 1 lines of input.
- The first line of each test case contains two space-separated integers N, M.
- M lines follow. For each valid i, the i^{th} of these lines contains two space-separated integers x_{i}, y_{i} - parameters of the i^{th} operation.

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

For each test case, output in a single line the maximum sum of integers of the array A after M operations.

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

$1 ≤ T ≤ 12600$
$1 ≤ N ≤ 10^{9}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ x_{i} ≤ 10^{9}$
$2 ≤ y_{i} ≤ 10^{9}$
- The sum of $M$ over all test cases does not exceed $10^{6}$.

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

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3
10 1
5 2
8 2
5 2
6 3
3 2
2 2
1 3
----- Sample Output 1 ------ 
25
41
5
----- explanation 1 ------ 
Test case $1$: Optimal filling is $[5, 0, 5, 0, 5, 0, 5, 0, 5, 0]$.

Test case $2$: Optimal filling is $[6, 6, 5, 6, 6, 0, 6, 6]$.

Test case $3$: Optimal filling is $[2, 1, 2]$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	operations = [list(map(int, input().split())) for i in range(m)]
	operations.sort(key=lambda x: x[0], reverse=True)
	ans = 0
	running_lcm = 1
	empty_spots = n
	for (x, y) in operations:
		running_lcm = lcm(running_lcm, y)
		ans += (empty_spots - n // running_lcm) * x
		empty_spots -= empty_spots - n // running_lcm
		if not empty_spots:
			break
	print(ans)


import math
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	(x, y, b, s, l, n, m, lc, nu, D, f) = ([], [], 0, 0, 1, 0, 0, 1, N, 0, 0)
	for j in range(M):
		(z, a) = map(int, input().split())
		x.append(z)
		y.append(a)
	li = []
	for i in range(M):
		li.append([x[i], i])
	li.sort()
	while D < M:
		m = li[-1][0]
		n = y[li[-1][1]]
		lc = lc * n // math.gcd(lc, n)
		s = s + m * (nu - N // lc)
		nu = N // lc
		if nu == 0:
			break
		li.pop(-1)
		D += 1
	print(s)


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

def lcm(a, b):
	return a // gcd(a, b) * b
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for k in range(m):
		(a, b) = map(int, input().split())
		arr.append([a, b])
	arr.sort(key=lambda x: x[0], reverse=True)
	(low, res, high) = (1, 0, n)
	for j in range(0, m):
		if high > 0:
			low = lcm(arr[j][1], low)
			high = high // low * low
			temp = high // low
			res += (n - temp) * arr[j][0]
			n = temp
	print(res)


from math import gcd
for t in range(int(input())):
	(n, m) = map(int, input().split())
	query = []
	for i in range(m):
		query.append(list(map(int, input().split())))
	query.sort(reverse=True)
	ans = 0
	pp = 1
	z = n
	for (x, y) in query:
		if z == 0:
			break
		pp = pp * y // gcd(pp, y)
		number_of_x = z - n // pp
		ans += number_of_x * x
		z -= number_of_x
	print(ans)


t = int(input())

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

def MyFunc(n):
	return n[0]
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(m):
		arr.append([int(x) for x in input().split()])
	arr.sort(key=MyFunc, reverse=True)
	l = 1
	rem = n
	res = 0
	i = 0
	while i < m and rem > 0:
		a = arr[i][0]
		b = arr[i][1]
		l = l * b // gcd(l, b)
		res += (rem - n // l) * a
		rem = n // l
		i += 1
	print(int(res))


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

def LCM(a, b):
	return a * b // gcd(a, b)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(0, m):
		(x, y) = map(int, input().split())
		a = []
		a.append(x)
		a.append(y)
		l.append(a)
	l.sort(reverse=True)
	i = 0
	sum1 = 0
	rem = n
	lcm = 1
	while rem > 0 and i < m:
		x = l[i][0]
		y = l[i][1]
		if i == 0:
			sum1 += (n - n // y) * x
			rem = n // y
			lcm = y
		else:
			lcm = LCM(lcm, y)
			sum1 += max(0, (rem - n // lcm) * x)
			rem = n // lcm
		i += 1
	print(sum1)


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

def lcm(a, b):
	return a // gdc(a, b) * b
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	Arr = []
	for i in range(m):
		(x, y) = map(int, input().split())
		Arr.append([x, y])
	Arr.sort(key=lambda x: x[0], reverse=True)
	temp = 1
	sum = 0
	val = n
	for j in range(m):
		if val > 0:
			temp = lcm(temp, Arr[j][1])
			remaining = n // temp
			filled_this_time = val - remaining
			sum += filled_this_time * Arr[j][0]
			val -= filled_this_time
	print(sum)


def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = read_int()
for case_num in range(t):
	(n, m) = read_ints()
	ops = []
	for i in range(m):
		(x, y) = read_ints()
		ops.append((x, y))
	ops.sort(reverse=True)
	ans = 0
	g = 1
	rem = n
	for (x, y) in ops:
		g1 = g * y // gcd(g, y)
		if g1 == g:
			continue
		drem = rem - n // g1
		rem = n // g1
		ans += drem * x
		if g1 > n:
			break
		g = g1
	print(ans)


from math import gcd
t = int(input())
for test in range(t):
	(n, m) = list(map(int, input().split()))
	l = []
	for i in range(m):
		num = list(map(int, input().split()))
		l.append(num)
	l.sort(reverse=True)
	li = 1
	s = 0
	pos = n
	for i in l:
		li = li * i[1] // gcd(li, i[1])
		if pos > 0:
			pos = pos - n // li
			s += pos * i[0]
			pos = n // li
		else:
			break
	print(s)


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr = sorted([list(map(int, input().split())) for k in range(m)], key=lambda x: x[0], reverse=True)
	(low, res, high) = (1, 0, n)
	for j in range(m):
		if high > 0:
			low = lcm(arr[j][1], low)
			high = high // low * low
			temp = high // low
			res += (n - temp) * arr[j][0]
			n = temp
	print(res)


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

def lcm(a, b):
	return int(a / gcd(a, b) * b)
T = int(input())
for _ in range(T):
	(N, M) = [int(n) for n in input().split()]
	left_out = N
	xy = []
	for _ in range(M):
		xy.append([int(n) for n in input().split()])
	xy = sorted(xy, key=lambda x: x[0])
	xy.reverse()
	mul = 1
	sum = 0
	for item in xy:
		mul = lcm(mul, item[1])
		sum += (left_out - N // mul) * item[0]
		left_out = N // mul
		if left_out == 0:
			break
	print(sum)


import math as mt
MAXN = 100001

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 getPrimesFromSpf():
	p = set()
	for x in spf:
		if x not in p:
			p.add(x)
	p.remove(0)
	p.remove(1)
	return sorted(list(p))

def getFactorization(x):
	ret = list()
	while x >= MAXN:
		sqrt_x = int(x ** 0.5)
		divisible = False
		for p in primes:
			if p > sqrt_x:
				break
			if not x % p:
				ret.append(p)
				x //= p
				divisible = True
				break
		if not divisible:
			ret.append(x)
			x //= x
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
spf = [0 for i in range(MAXN)]
sieve()
primes = getPrimesFromSpf()

def temp():
	sum_A = 0
	n = N
	gcd = {}
	XY.sort(reverse=True)
	for (x, y) in XY:
		factors = getFactorization(y)
		fact_dic = {}
		for factor in factors:
			if factor in fact_dic:
				fact_dic[factor] += 1
			else:
				fact_dic[factor] = 1
		new_fact = {}
		for fact in fact_dic:
			if fact in gcd:
				if fact_dic[fact] > gcd[fact]:
					new_fact[fact] = fact_dic[fact] - gcd[fact]
					gcd[fact] = fact_dic[fact]
			else:
				gcd[fact] = fact_dic[fact]
				new_fact[fact] = fact_dic[fact]
		yy = 1
		for fact in new_fact:
			yy *= fact * new_fact[fact]
		temp = n // yy
		sum_A += (n - temp) * x
		n = temp
		mul_gcd = 1
		for fact in gcd:
			mul_gcd *= fact * gcd[fact]
		if mul_gcd > N:
			break
	return sum_A
for _ in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	XY = [[int(x) for x in input().split()] for i in range(M)]
	XY = [[x, y] for [x, y] in XY if y != 1]
	print(temp())


import math
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	ar = []
	for i in range(M):
		(x, y) = map(int, input().split())
		ar.append([x, y])
	ar.sort(reverse=True)
	l = 1
	rem = N
	res = 0
	for i in range(M):
		if rem > 0:
			a = ar[i][0]
			b = ar[i][1]
			l = l * b // math.gcd(l, b)
			res += (rem - N // l) * a
			rem = N // l
	print(int(res))


from math import *

def lcm(x, y):
	return x * y // gcd(x, y)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = []
	for __ in range(m):
		(X, Y) = map(int, input().split())
		A.append([X, Y])
	A.sort(reverse=True)
	myLCM = 1
	sum = 0
	myN = n
	for (x, y) in A:
		myLCM = lcm(myLCM, y)
		if myN > 0:
			sum += (myN - n // myLCM) * x
			myN = n // myLCM
		else:
			break
	print(sum)


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

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	pairs = []
	for _ in range(M):
		(x, y) = map(int, input().split())
		pairs.append((x, y))
	pairs.sort(reverse=True)
	zero_gap = 1
	total = 0
	for (x, y) in pairs:
		if zero_gap > N:
			break
		new_zero_gap = lcm(zero_gap, y)
		total += x * (N // zero_gap - N // new_zero_gap)
		zero_gap = new_zero_gap
	print(total)


from collections import Counter
import math
from bisect import bisect
MOD = pow(10, 9) + 7
MAX = pow(10, 20)
MIN = -pow(10, 20)

class get:

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

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

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

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

def solve():
	(n, m) = get.map()
	mylist = [0] * m
	for i in range(m):
		(x, y) = get.map()
		mylist[i] = [x, y]
	mylist.sort(reverse=True)
	lcm = 1
	sum_ = 0
	for i in range(m):
		vacant_space = n // lcm
		if not vacant_space:
			break
		lcm = LCM(lcm, mylist[i][1])
		sum_ += (vacant_space - n // lcm) * mylist[i][0]
	print(sum_)
for _ in range(int(input())):
	solve()


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

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

def prog_name():
	(n, m) = map(int, input().split())
	operations = []
	for x in range(m):
		temp = list(map(int, input().split()))
		operations.append(temp)
	operations.sort(reverse=True)
	ans = 0
	ll = 1
	temp = n
	for x in operations:
		if temp > 0:
			ll = lcm(ll, x[1])
			ans += (temp - n // ll) * x[0]
			temp = n // ll
		else:
			break
	print(ans)
T = int(input())
for unique in range(T):
	prog_name()


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

def LCM(a, b):
	return int(a / GCD(a, b) * b)
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	Opr_list = []
	for i in range(M):
		(x, y) = list(map(int, input().split()))
		Opr_list.append([x, y])
	Opr_list = sorted(Opr_list, key=lambda x: x[0], reverse=True)
	ans = 0
	Prev_Empyt = N
	product = 1
	for j in range(M):
		(x, y) = Opr_list[j]
		if Prev_Empyt == 0:
			break
		if product % y == 0:
			continue
		product = LCM(product, y)
		Cur_Empty = N // product
		SUM = (Prev_Empyt - Cur_Empty) * x
		Prev_Empyt = Cur_Empty
		ans = ans + SUM
	print(ans)


T = int(input())

def lcm(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	return int(a * b // gcd(a, b))

def gcd(a, b):
	if b == 0:
		return a
	if a == 0:
		return b
	r = a % b
	while r:
		a = b
		b = r
		r = a % b
	return b
for t in range(T):
	(N, M) = map(int, input().split(' '))
	ops = []
	for m in range(M):
		(x, y) = map(int, input().split(' '))
		ops.append((x, y))
	ops.sort(key=lambda o: o[0], reverse=True)
	(xi, yi) = ops[0]
	zeros = N // yi
	tot = (N - zeros) * xi
	prev = yi
	zeros_up = zeros
	for (xi, yi) in ops[1:]:
		cm = lcm(yi, prev)
		zeros_up = N // cm
		tot += (zeros - zeros_up) * xi
		zeros = zeros_up
		prev = cm
		if not zeros_up:
			break
	print(tot)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for k in range(int(input())):
	(n, m) = map(int, input().split())
	l1 = []
	for j in range(m):
		lj = list(map(int, input().split()))
		l1.append(lj)
	l1.sort(reverse=True)
	i = 0
	sum = 0
	j = n
	lcm = 1
	while i < m and j > 0:
		a = l1[i][0]
		b = l1[i][1]
		lcm = lcm * b // gcd(lcm, b)
		sum += (j - n // lcm) * a
		j = n // lcm
		i += 1
	print(int(sum))


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(m):
		(x, y) = map(int, input().split())
		l.append([x, y])
	l.sort(key=lambda p: p[0], reverse=True)
	ans = 0
	rem = n
	ans += (rem - n // l[0][1]) * l[0][0]
	prev = l[0][1]
	rem = n // l[0][1]
	for i in range(1, m):
		if rem == 0:
			break
		kk = l[i][1]
		z = math.gcd(prev, kk)
		if False:
			ans += rem * l[i][0]
			break
		else:
			lcm = prev * kk // z
			ans += (rem - n // lcm) * l[i][0]
			rem = n // lcm
			prev = lcm
	print(ans)


import math
import operator
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	x = []
	z = []
	for i in range(m):
		(a, b) = map(int, input().split(' '))
		x.append([a, b])
	x.sort(reverse=True)
	sum = 0
	div = n
	l = 1
	for i in range(m):
		if div <= 0:
			break
		x1 = x[i][0]
		x2 = x[i][1]
		l = l * x2 // math.gcd(l, x2)
		sum += (div - n // l) * x1
		div = n // l
	print(sum)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(m):
		l.append(list(map(int, input().split())))
	l.sort(reverse=True)
	temp = 1
	rem = n
	tot = 0
	i = 0
	while i < m and rem > 0:
		x = l[i][0]
		y = l[i][1]
		temp = temp * y // math.gcd(temp, y)
		tot += (rem - n // temp) * x
		rem = n // temp
		i += 1
	print(tot)


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(m):
		(t1, t2) = map(int, input().split())
		arr.append([t1, t2])
	arr.sort(reverse=True)
	(temp1, temp2, ans) = (1, n, 0)
	for i in range(m):
		temp1 = temp1 * arr[i][1] // gcd(temp1, arr[i][1])
		ans += (temp2 - n // temp1) * arr[i][0]
		temp2 = n // temp1
		if temp2 <= 0:
			break
	print(ans)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(m):
		(x, y) = map(int, input().split())
		a.append((x, y))
	a.sort(reverse=True)
	ans = 0
	t = 1
	d = 0
	for i in range(m):
		t = t * a[i][1] // math.gcd(t, a[i][1])
		k = n // t
		d2 = n - k
		d1 = d2 - d
		d = d2
		ans += a[i][0] * d1
		if d == n:
			break
	print(ans)


import math
for _ in range(int(input())):
	arr1 = []
	(n, m) = map(int, input().split())
	for i in range(m):
		(x, y) = map(int, input().split())
		arr1.append([x, y])
	arr1.sort(reverse=True)
	(c, rem, out) = (1, n, 0)
	i = 0
	while i < m and rem > 0:
		(a, b) = (arr1[i][0], arr1[i][1])
		c = c * b // math.gcd(c, b)
		out += (rem - n // c) * a
		rem = n // c
		i += 1
	print(out)


import math

def pos(y, n):
	temp = n - n % y
	new = n - temp // y
	return new
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		l.append((x, y))
	l.sort(reverse=True)
	empty = n
	x1 = l[0][0]
	y1 = l[0][1]
	tot = x1 * pos(y1, n)
	empty -= pos(y1, n)
	for i in range(1, m):
		x = l[i][0]
		y = l[i][1]
		lcm = y1 * y // math.gcd(y1, y)
		new = n - pos(lcm, n)
		tot += (empty - new) * x
		empty = new
		y1 = lcm
		if not empty:
			break
	print(tot)


import math
t = int(input())
for i in range(0, t):
	L = []
	(n, m) = map(int, input().split())
	maxi = -1
	pos = -1
	s = 0
	for j in range(0, m):
		(x, y) = map(int, input().split())
		L.append((-1 * x, y))
	L.sort()
	for j in range(0, m):
		L[j] = (abs(L[j][0]), abs(L[j][1]))
	l = 1
	l1 = 1
	u = 0
	while u < len(L) and l <= n:
		l = l * L[u][1] // math.gcd(l, L[u][1])
		s += L[u][0] * (n // l1 - n // l)
		l1 = l
		u += 1
	print(s)


from math import gcd
t = int(input())
while t:
	(n, m) = map(int, input().split())
	operations = []
	for i in range(0, m):
		operations.append(list(map(int, input().split())))
	operations = sorted(operations, reverse=True)
	lcmY = 1
	maxSum = 0
	remainingZeros = n
	i = 0
	while i < m and remainingZeros > 0:
		x = operations[i][0]
		y = operations[i][1]
		lcmY *= y // gcd(lcmY, y)
		maxSum += (remainingZeros - n // lcmY) * x
		remainingZeros = n // lcmY
		i += 1
	print(maxSum)
	t -= 1


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(m):
		(x, y) = map(int, input().split())
		if y in d:
			if x > d[y]:
				d[y] = x
		else:
			d[y] = x
	arr = list(d.items())
	arr.sort(reverse=True, key=lambda x: x[1])
	m = len(arr)
	p = n
	k = 1
	ans = 0
	i = 0
	while i < m and n > 0:
		a = arr[i][1]
		b = arr[i][0]
		k = k * b // math.gcd(k, b)
		ans += a * (n - p // k)
		n = p // k
		i += 1
	print(ans)


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	xa = []
	yb = []
	for i in range(m):
		(x, y) = map(int, input().split())
		xa.append(x)
		yb.append(y)
	v = sorted(list(zip(xa, yb)))
	v = v[::-1]
	lcm = 1
	r = n
	res = 0
	for i in range(m):
		if r <= 0:
			break
		a = v[i][0]
		b = v[i][1]
		lcm = lcm * b // math.gcd(lcm, b)
		res = res + (r - n // lcm) * a
		r = n // lcm
	print(res)


import math

def solve():
	(n, m) = map(int, input().split())
	a = []
	b = []
	for i in range(m):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	c = zip(a, b)
	c = list(c)
	c = sorted(c)
	c = c[::-1]
	lcm = 1
	rem = n
	res = 0
	for i in range(m):
		if rem <= 0:
			break
		p = c[i][0]
		q = c[i][1]
		lcm = lcm * q // math.gcd(lcm, q)
		res = res + (rem - n // lcm) * p
		rem = n // lcm
	print(res)
t = int(input())
for i in range(t):
	solve()


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while b % a != 0:
		(a, b) = (b % a, a)
	return a
T = int(input())
for iter in range(T):
	(n, m) = map(int, input().split())
	li = []
	for temp in range(m):
		(x, y) = map(int, input().split())
		li.append((x, y))
	li.sort(reverse=True)
	sum = 0
	lcm = 1
	unfilled = n
	j = 0
	while unfilled > 0 and j < m:
		x = li[j][0]
		y = li[j][1]
		lcm = lcm * y // gcd(lcm, y)
		value = unfilled - n // lcm
		unfilled = n // lcm
		sum += x * value
		j += 1
	print(sum)


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

def lcm(a, b):
	return a / gcd(a, b) * b
t = input()
t = int(t)
for i in range(t):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	d = []
	for j in range(m):
		(x, y) = input().split(' ')
		x = int(x)
		y = int(y)
		d.append([x, y])
	d = sorted(d, key=lambda x: x[0], reverse=True)
	sk = 1
	r = n
	s = 0
	j = 0
	while n > 0 and j < len(d):
		sk = int(sk * d[j][1]) / gcd(sk, d[j][1])
		s = s + d[j][0] * (n - int(r / sk))
		n = int(r / sk)
		j = j + 1
	print(s)


def gcd(p, q):
	if p == 0:
		return q
	return gcd(q % p, p)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = dict()
	for s in range(m):
		(x, y) = map(int, input().split())
		if y in d:
			d[y] = max(d[y], x)
		else:
			d[y] = x
	p = sorted(d.items(), key=lambda l: (l[1], l[0]), reverse=True)
	t = n
	ans = 0
	c = 1
	for i in range(len(p)):
		c = c * p[i][0] // gcd(c, p[i][0])
		g = n - t // c
		n = t // c
		ans += g * p[i][1]
		if n <= 0:
			break
	print(ans)


import math

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, str(input()).split()))
	ar = [0] * k
	for i in range(k):
		ar[i] = list(map(int, str(input()).split()))
	ar.sort(reverse=True)
	rem = n
	l = 1
	cou = 0
	for i in range(k):
		if rem <= 0:
			break
		a = ar[i][0]
		b = ar[i][1]
		l = lcm(l, b)
		cou += (rem - n // l) * a
		rem = n // l
	print(cou)


import math
for _ in range(int(input())):
	arr = []
	(n, m) = map(int, input().split())
	for i in range(m):
		l = list(map(int, input().split()))
		arr.append(l)
	arr.sort(reverse=True)
	ans = 0
	length = n
	mul = 1
	for i in range(0, m):
		if length <= 0:
			break
		mul = mul * arr[i][1] // math.gcd(mul, arr[i][1])
		ans += (length - n // mul) * arr[i][0]
		length = n // mul
	print(ans)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t1 = int(input())
while t1 > 0:
	(n, M) = tuple(map(int, input().split(' ')))
	dt = dict()
	for mi in range(1, M + 1):
		(x, y) = tuple(map(int, input().split(' ')))
		if y in dt.keys():
			if dt[y] < x:
				dt[y] = x
		else:
			dt[y] = x
	yx = sorted(dt.items(), key=lambda x: x[1], reverse=True)
	suma = 0
	mul = dd = 1
	rn = n
	for (y, x) in yx:
		hcf = gcd(dd, y)
		dd = int(dd * y / hcf)
		t = rn - n // dd
		suma = suma + t * x
		rn = rn - t
		if rn < 1:
			break
	print(suma)
	t1 = t1 - 1


import math
xiyi = []
testcases = int(input())
for i in range(testcases):
	(N, M) = map(int, input().split())
	for j in range(M):
		xiyi.append(list(map(int, input().split())))
	xiyi.sort(reverse=True)
	y_prod = int(1)
	sum1 = int(N * xiyi[0][0])
	for k in range(M):
		y_prod *= xiyi[k][1] // math.gcd(y_prod, xiyi[k][1])
		if N // y_prod == 0:
			break
		if k < M - 1:
			sum1 += (xiyi[k + 1][0] - xiyi[k][0]) * (N // y_prod)
		else:
			sum1 += (0 - xiyi[k][0]) * (N // y_prod)
	print(sum1)
	xiyi.clear()


import math
t1 = int(input())
while t1 > 0:
	(n, m) = tuple(map(int, input().split(' ')))
	mdict = dict()
	for mi in range(1, m + 1):
		(x, y) = tuple(map(int, input().split(' ')))
		if y in mdict.keys():
			if mdict[y] < x:
				mdict[y] = x
		else:
			mdict[y] = x
	yx = sorted(mdict.items(), key=lambda x: x[1], reverse=True)
	suma = 0
	mul = 1
	z = 1
	rn = n
	for (y, x) in yx:
		z = int(z * y / math.gcd(z, y))
		t = rn - n // z
		suma = suma + t * x
		rn = rn - t
		if rn < 1:
			break
	print(suma)
	t1 = t1 - 1


t = int(input())
for _ in range(t):
	inp1 = input()
	l1 = inp1.split(' ')
	n = int(l1[0])
	m = int(l1[1])
	ops = []
	for i in range(m):
		inp2 = input()
		l2 = inp2.split(' ')
		ops.append([int(l2[0]), int(l2[1])])
	ops = sorted(ops, reverse=True)
	lcm = 1
	k = n
	s = 0
	for i in range(m):
		if k > 0:
			num1 = ops[i][0]
			num2 = ops[i][1]
			a = max(lcm, num2)
			b = min(lcm, num2)
			r = 1
			while r != 0:
				r = a % b
				if r == 0:
					gcd = b
					break
				(a, b) = (b, r)
			lcm = lcm * num2 // gcd
			s = s + (k - n // lcm) * num1
			k = n // lcm
	print(s)


import sys
I = lambda x=' ': map(int, sys.stdin.readline().split(x))
pr = lambda *x, ch=' ': sys.stdout.write(f'{ch.join(map(str, x))}\n')
from math import gcd

def solve():
	(n, m) = I()
	a = []
	for _ in range(m):
		tmp = [*I()]
		a.append(tmp)
	a.sort(key=lambda x: x[0], reverse=True)
	prev = a[0][1]
	s = a[0][0] * (n - n // a[0][1])
	for i in range(1, m):
		if prev % a[i][1] == 0:
			continue
		if prev > n:
			break
		x = n // prev
		factor = a[i][1] // gcd(a[i][1], prev)
		s += a[i][0] * (x - x // factor)
		prev *= factor
	pr(s)

def main():
	(t,) = I()
	for _ in range(t):
		solve()
main()


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	lis = []
	(n, q1) = map(int, input().split())
	for _ in range(q1):
		lis.append(list(map(int, input().split())))
	lis.sort()
	q = n // lis[-1][1]
	su = lis[-1][0] * (n - q)
	va = lis[-1][1]
	re = q
	la = q * lis[-1][1]
	for i1 in range(q1 - 2, -1, -1):
		if re == 0:
			break
		elif va % lis[i1][1] == 0:
			pass
		elif lis[i1][1] % va == 0:
			q = la // lis[i1][1]
			su += lis[i1][0] * (re - q)
			re = q
			va = lis[i1][1]
			la = q * va
		else:
			gc = gcd(va, lis[i1][1])
			lcm = va * lis[i1][1] // gc
			q = la // lcm
			su += lis[i1][0] * (re - q)
			re = q
			va = lcm
			la = q * va
	print(su)


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

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm

def function():
	(size, num) = map(int, input().split())
	lst = []
	for _ in range(num):
		(x, y) = map(int, input().split())
		lst.append([x, y])
	lst.sort(key=lambda x: x[0], reverse=True)
	rem = size
	lcm = 1
	res = 0
	i = 0
	while i < num and rem > 0:
		a = lst[i][0]
		b = lst[i][1]
		lcm = compute_lcm(lcm, b)
		res += (rem - size // lcm) * a
		rem = size // lcm
		i += 1
	print(res)
test = int(input())
while test != 0:
	function()
	test -= 1


import sys
from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
T = int(sys.stdin.readline())
for x in range(T):
	(N, M) = map(int, sys.stdin.readline().split())
	B = []
	for i in range(M):
		B.append(list(map(int, sys.stdin.readline().split())))
	B = sorted(B, key=lambda x: x[0])
	key = B[M - 1][1]
	count = N // key
	ans = (N - count) * B[M - 1][0]
	op = M - 2
	while count != 0 and op >= 0:
		if key % B[op][1] == 0:
			op -= 1
			continue
		else:
			newkey = lcm(key, B[op][1])
			newcount = count * key // newkey
			ans += B[op][0] * (count - count * key // newkey)
			key = newkey
			count = newcount
			op -= 1
	sys.stdout.write(str(ans) + '\n')


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for j in range(m):
		(x, y) = map(int, input().split())
		a.append((x, y))
	a.sort()
	a.reverse()
	lcm = 1
	ans = 0
	d = n
	for j in range(m):
		if n <= 0:
			break
		g = a[j][0]
		h = a[j][1]
		lcm = lcm * h // math.gcd(lcm, h)
		ans += g * (n - d // lcm)
		n = d // lcm
		if n <= 0:
			break
	print(ans)


from math import gcd
import operator
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	x = []
	res = 0
	lcm = 1
	rem = n
	for j in range(m):
		(a, b) = map(int, input().split())
		x.append([a, b])
	x.sort(reverse=True, key=operator.itemgetter(0))
	for i in range(m):
		if rem <= 0:
			break
		(a, b) = (x[i][0], x[i][1])
		lcm = int(lcm * b / gcd(lcm, b))
		res += int((rem - int(n / lcm)) * a)
		rem = int(n / lcm)
	print(res)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(m1, x, y, total) = (m, [], [], 0)
	while m != 0:
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
		m -= 1
	(x, y) = map(list, zip(*sorted(zip(x, y))))
	lcm = y[-1]
	left = n // lcm
	r = n - left
	total += r * x[-1]
	for i in range(m1 - 2, -1, -1):
		gcd = math.gcd(lcm, y[i])
		lcm = lcm * y[i] // gcd
		r = left - n // lcm
		left = n // lcm
		total += r * x[i]
		if left == 0:
			break
	print(total)


import math
from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	a = []
	b = []
	lcmm = 0
	d = defaultdict(lambda : [])
	total = 0
	preremaining = 0
	heap_1 = []
	for i in range(m):
		(x, y) = map(int, input().strip().split())
		a.append(x)
		b.append(y)
	for i in range(len(a)):
		d[a[i]].append(b[i])
	xx = sorted(d.keys())
	for i in range(len(xx)):
		for j in d[xx[i]]:
			heap_1.append([xx[i], j])
	for i in range(len(heap_1) - 1, -1, -1):
		x = heap_1[i][0]
		y = heap_1[i][1]
		if lcmm == 0:
			total += (n - n // y) * x
			preremaining = n // y
			lcmm = y
		else:
			if preremaining == 0:
				break
			lcmm = lcmm * y // math.gcd(lcmm, y)
			postremaining = n // lcmm
			total += (preremaining - postremaining) * x
			preremaining = postremaining
	print(int(total))


from collections import defaultdict
from math import gcd
import sys
for _ in range(int(sys.stdin.readline())):
	(n, m) = map(int, sys.stdin.readline().split())
	d = defaultdict(lambda : 0)
	for i in range(m):
		(x, y) = map(int, sys.stdin.readline().split())
		d[y] = max(d[y], x)
	l = []
	for (x, y) in d.items():
		l.append([y, x])
	l.sort(reverse=True)
	lcm = l[0][-1]
	left = n // lcm
	ans = (n - left) * l[0][0]
	for i in range(1, len(l)):
		if left <= 0:
			break
		lcm = lcm * l[i][1] // gcd(lcm, l[i][1])
		ans += (left - n // lcm) * l[i][0]
		left = n // lcm
	sys.stdout.write(str(ans) + '\n')


import math
T = int(input())
for _ in range(T):
	inps = [int(z) for z in input().split()]
	(N, M) = (inps[0], inps[1])
	store_op = []
	for i in range(M):
		temp_inp = [int(z) for z in input().split()]
		store_op.append(temp_inp)
	store_op = sorted(store_op, reverse=True)
	lcm = 1
	Sum = 0
	for ele in store_op:
		(x, y) = (ele[0], ele[1])
		if lcm % y == 0:
			continue
		if lcm > N:
			break
		temp_lcm = int(lcm * y / math.gcd(lcm, y))
		Sum += x * (int(N / lcm) - int(N / temp_lcm))
		lcm = temp_lcm
	print(Sum)


import sys
from math import gcd
input = sys.stdin.readline
t = int(input().rstrip())
for __ in range(t):
	(n, m) = map(int, input().rstrip().split(' '))
	arr = []
	for __ in range(m):
		(x, y) = map(int, input().rstrip().split(' '))
		arr.append((x, y))
	res = 0
	curr_factor = 1
	arr.sort(key=lambda x: (-x[0], x[1]))
	for (x, y) in arr:
		curr_y = gcd(curr_factor, y)
		curr_y = y // curr_y
		if not n:
			break
		res += x * (n - n // curr_y)
		n //= curr_y
		curr_factor *= curr_y
	print(res)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	query = []
	for i in range(m):
		query.append(list(map(int, input().split())))
	query.sort(reverse=True)
	res = 0
	curr_product = 1
	curr_size = n
	for (x, y) in query:
		if curr_size < 1:
			break
		curr_product = curr_product * y // math.gcd(curr_product, y)
		count_x = curr_size - n // curr_product
		res += count_x * x
		curr_size -= count_x
	print(res)


import operator
import collections
import math
t = int(input())
while t:
	(n, m) = map(int, input().split())
	l = []
	for i in range(m):
		(x, y) = map(int, input().split())
		l.append((x, y))
	sorted_d = sorted(l, key=lambda x: x[0], reverse=True)
	count = 0
	p = 1
	s = 0
	for (x, y) in sorted_d:
		p = p * y // math.gcd(p, y)
		temp = n // p
		num_avail = n - count - temp
		s += num_avail * x
		count += num_avail
		if count == n:
			break
	print(s)
	t -= 1


import math
t = int(input().strip())
for _ in range(0, t):
	[N, M] = list(map(int, input().strip().split()))
	l = []
	for _ in range(0, M):
		[x, y] = list(map(int, input().strip().split()))
		l.append((x, y))
	l = sorted(l, key=lambda x: x[0], reverse=True)
	count = 0
	s = 0
	p = 1
	for (x, y) in l:
		p = p * y // math.gcd(p, y)
		temp = N // p
		num_avail = N - count - temp
		s += num_avail * x
		count += num_avail
		if count == N:
			break
	print(s)


def find(x, y):
	while y != 0:
		temp = y
		y = x % y
		x = temp
	return x
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	temp = n
	l = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		l.append([x, y])
	l.sort(reverse=True)
	ans = 0
	lcm = 1
	for i in l:
		lcm = lcm * i[1] // find(lcm, i[1])
		ans = ans + i[0] * (n - temp // lcm)
		n = temp // lcm
		if n == 0:
			break
	print(ans)


import math

def ans(arr, s, m, size, n):
	a = arr[0][1]
	lcm = arr[0][1]
	for i in range(1, m):
		if size <= 0:
			print(s)
			return
		b = arr[i][1]
		x = arr[i][0]
		gcd = math.gcd(a, b)
		lcm = a // gcd * b
		a = lcm
		if lcm > n:
			s += x * size
			print(s)
			return
		size -= n // lcm
		q = n // lcm
		n = q * lcm
		s += x * size
		size = q
	print(s)
t = int(input())
for k in range(t):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	arr = []
	flag = 0
	for o in range(m):
		arr.append(list(map(int, input().rstrip().split())))
	arr.sort(key=lambda list: list[0], reverse=True)
	size = n // arr[0][1]
	s = arr[0][0] * n - arr[0][0] * size
	ans(arr, s, m, size, n)


def hello():
	t = int(input())
	answer = []
	if t >= 1 and t <= 12600:
		for x in range(t):
			list1 = list(map(int, input().split(' ')))
			n = list1[0]
			m = list1[1]
			if n >= 1 and n <= 10 ** 9:
				if m >= 1 and m <= 10 ** 5:
					list1 = []
					for i in range(m):
						list1.append(list(map(int, input().split(' '))))
					flag = True
					for i in list1:
						if i[0] < 1 or i[0] > 10 ** 9:
							flag = False
							break
						if i[1] < 2 or i[1] > 10 ** 9:
							flag = False
							break
					if flag == False:
						continue
					list1.sort(key=lambda x: x[0])
					list1 = list1[::-1]
					Dict = {}
					k = 1
					c = n
					summ = 0
					for i in list1:
						if Dict.get(i[1]):
							continue
						k = k // gcd(k, i[1]) * i[1]
						summ = summ + (c - n // k) * i[0]
						c = n // k
						if c <= 0:
							break
						Dict[i[1]] = 0
			answer.append(summ)
		for i in answer:
			print(i)

def gcd(A, B):
	if A == 0:
		return B
	return gcd(B % A, A)
hello()