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:
def check_root(n, d):
	"""check if discriminant is non-negative"""
	return (n*n + 2*n + 1 >= 4*d)
	
def mod_expo(n, p, m):
	"""find (n^p)%m"""
	result = 1
	while p != 0:
		if p%2 == 1:
			result = (result * n)%m
		p //= 2
		n = (n * n)%m
	return result
	
def find_product(n, m, arr):
	"""find |arr i - arr j| mod m"""
	product=1
	if n <= m:
		for i in range(n):
			for j in range(i+1, n):
				 product = (product * abs(arr[i] - arr[j]))%m
		return product
	return 0

def find_subarrays(n, k, word):
	"""find subarrays with sum k"""
	curr_sum = 0
	count = 0
	mp = {}
	for i in range(n):
		curr_sum += int(word[i])
		if curr_sum not in mp:
			mp[curr_sum] = 0
		mp[curr_sum] += 1
		if curr_sum == k:
			count += 1
		elif (curr_sum - k) in mp:
			count += mp[(curr_sum - k)]
	return count
	
def construct(a, b):
	unequal = []
	for i in range(a*b):
		unequal.append(False)
	for i in range(a*b):
		if (i%a)%b  != (i%b)%a:
			unequal[i] = True
	return unequal
	
def __init__(a, b):
	pref_sum = []
	unequal = construct(a, b)
	pref_sum.append(int(unequal[0]))
	for i in range(1, a*b):
		pref_sum.append(pref_sum[i-1] + int(unequal[i]))
	return pref_sum
	
def get_count(a, b, n, pref_sum):
	total = (n//(a*b))*pref_sum[a*b-1] + pref_sum[n%(a*b)]
	return total
t = 1
t = int(input())
while t:
	t = t - 1
	# k = int(input())
	# a, b, m = map(int, input().split())
	l = list(map(int, input().strip().split()))[:3]
	a = int(l[0])
	b = int(l[1])
	m = int(l[2])
	
	ans = []
	pref_sum = __init__(a, b)
	for i in range(m):
		x, y = map(int, input().split())
		ans.append(get_count(a, b, y, pref_sum) - 
				   get_count(a, b, x-1, pref_sum))
	print(*ans, sep=' ')