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 soln_slow(a, b, n, l):
    ct = 0
    for x in range(1, n+1):
        if (((x % a) % b) == ((x % b) % a)):
            print(x, "yes")
        else:
            ct += 1
            print(x, "no")
    return ct

# after every multliple of _b_ that is not a multiple of _a_ we see _b_
def soln(a, b, n, l):
    mb = n // b 
    mbn = mb * b
    ml = n // l 
    #print(locals())
    if (mbn != (ml * l)):
        return max(((mb - 1) - ml)*b + min((n - mbn) + 1, b), 0)
    else:
        return max((mb - ml)*b, 0)

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


t = int(input())
for _ in range(t):
    a, b, q = map(int, input().split())
    if a > b:
        a,b = b,a
    lc = lcm(a,b)
    solns= []
    for __ in range(q):
        l, r = map(int, input().split())
        solns.append(soln(a, b, r, lc) - soln(a, b, l - 1, lc))
    print(" ".join(map(str, solns)))

        

#import itertools
#
#for a, b in itertools.product(range(1,10), range(1, 10)):
#    for z in range(1, a*b + 1):
#        if a > b:
#            a,b = b,a
#        lc = lcm(a,b)
#        s_slow = soln_slow(a,b,z,lc)
#        s_fast = soln(a,b,z,lc) 
#        if soln(a,b,z,lc) != soln_slow(a,b,z,lc):
#            print("ERROR", locals())