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:

class Soln:
    def __init__(self, a, b):
        self.a, self.b = a, b
        pSum = []
        for x in range(a * b):
            if len(pSum) == 0:
                curr = 0
            else:
                curr = pSum[-1]
            if (x % a) % b != (x % b) % a:
                curr += 1
            pSum.append(curr)
        self.pSum = pSum
    
    def brute(self, l, r):
        a, b = self.a, self.b
        result = 0
        for x in range(l, r + 1):
            if (x % a) % b != (x % b) % a:
                result += 1
        return result

    def mod(self, n):
        a, b = self.a, self.b
        return n % (a * b)

    def npSum(self, l, i):
        mod = self.mod
        a, b = self.a, self.b
        pSum = self.pSum
        lVal = 0 if l - 1 < 0 else pSum[l - 1]
        if i < a * b - l:
            return pSum[l + i] - lVal
        return pSum[a * b - 1] - lVal + pSum[ mod(l + i) ]

    def fast(self, l, r):
        mod = self.mod
        a, b = self.a, self.b
        if r - l < a * b:
            return self.npSum(
                mod(l), 
                mod(r - l),
            )
        N = (r - l) // (a * b)
        return N * self.npSum(
            mod(l),
            a * b - 1
        ) + self.npSum(
            mod(l),
            mod(r - l),
        )

def main():
    t = int(input())
    for _ in range(t):
        a, b, q = [int(x) for x in input().split(' ')]
        soln = Soln(a, b)
        result = []
        for _ in range(q):
            l, r = [int(x) for x in input().split(' ')]
            # curr = soln.brute(l, r)
            curr = soln.fast(l, r)
            result.append(curr)
        print(' '.join(str(x) for x in result))

# import random
# def randomTest():
#     T = 100
#     for i in range(1, T + 1):
#         a = random.randint(1, 20)
#         b = random.randint(1, 20)
#         l = random.randint(1, 1000)
#         r = random.randint(l + 1, 2000)
#         print(f'Case #{i}, {(a, b, l, r) = }')
#         s = Soln(a, b)
#         brute = s.brute(l, r)
#         fast = s.fast(l, r)
#         try:
#             assert(brute == fast)
#         except:
#             print('ERROR!')
#             print(f'{(brute, fast) = }')
#             break

if __name__ == '__main__':
    main()
    # randomTest()