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 
def gcd(a,b) :
    if a == 0 :
        return b
    return gcd(b%a ,a)
for T in range(int(input())) :
    a , b ,q = list(map(int,input().split()))
    g = gcd(a,b)
    hcf = (b*a)//g
    st =1
    end = b
    for i in range(q) :
        l,r = list(map(int,input().split()))
        maxi = max(a,b)
        if r <= hcf :
            if r < maxi :
                print(0 ,end =' ')
            else :
                print(r - maxi +1 ,end = ' ')
        else :
            st = 1
            m =1
            res = 0
            while st < l :
                st = hcf*m
                m +=1
            if st > r :
                st -= hcf
            end = st
            if st >l :
                res  = (st - l )
            else :
                res  = 0
            count = 0
            while True :
                if end >= r :
                    break
                elif end> l :
                    end += hcf
                    end += hcf
                    count += 1
                else :
                    end += hcf
                
            temp = r - max(st,l) - count*(maxi-1)

            print(res +temp ,end = ' ' )

    print('\n',end = '')
            
            
                
                
            
            
            
        
            
            
