Problem: You are given two integers a and b, and q queries. The i-th query consists of two numbers l_i and r_i, and the answer to it is the number of integers x such that l_i ≤ x ≤ r_i, and ((x mod a) mod b) ≠ ((x mod b) mod a). Calculate the answer for each query.

Recall that y mod z is the remainder of the division of y by z. For example, 5 mod 3 = 2, 7 mod 8 = 7, 9 mod 4 = 1, 9 mod 9 = 0.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then the test cases follow.

The first line of each test case contains three integers a, b and q (1 ≤ a, b ≤ 200; 1 ≤ q ≤ 500).

Then q lines follow, each containing two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10^{18}) for the corresponding query.

Output

For each test case, print q integers — the answers to the queries of this test case in the order they appear.

Example

Input


2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200


Output


0 0 0 2 4 
0 91 

Solution (in PYTHON3):

Solution:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

def gdc(a, b):
	while b != 0:
		a, b = b, a%b
	return a


t = int(input())
for _ in range(t):
	a, b, q = map(int, input().split())
	if a < b:
		a, b = b, a
	# print("a", a)
	# print("b", b)
	for i in range(q):
		l, r = map(int, input().split())
		nok = a * b // gdc(a, b)
		# if a % b  == 0:
		# 	print(0, end = " ")
		# else:
		left_border  = (l // nok) * nok

		right_border = (r // nok ) * nok
		ans = a * ( (right_border- left_border) // nok + 1)
		# print("inside ans", ans)

		# delete extra from rigth
		if right_border + a - 1 > r:
			ans -= (right_border + a - 1) - r
		# print("deleted from right", ans)

		# delete extra from left
		if left_border < l:
			ans -= min(a, l - left_border)
		# print("deleted from left", ans)
		print(r-l+1-ans, end = " ")
	print()


# sys.stdout.write(str(n)+"\n")