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 
"""T=int(input())
for _ in range(0,T):
    n=int(input())
    a,b=map(int,input().split())
    s=input()
    s=[int(x) for x in input().split()]
    for i in range(0,len(s)):
        a,b=map(int,input().split())"""


"""
import math
T=int(input())
for _ in range(0,T):
    A,B,q=map(int,input().split())
    a=min(A,B)
    b=max(A,B)
    L=[]
    for e in range(q):
        l,r=map(int,input().split())
        if(math.gcd(a,b)==a):
            L.append(0)
        else:
            t1=(l-b)//(a*b)
            if((l-b)%(a*b)!=0):
                t2=t1+1
            else:
                t2=t1
                t1-=1

            t4=(r-b)//(a*b)
            #print('t4',t4)
            if((r-b)%(a*b)!=0 and (b+(t4*a*b))+(a*b)<=r):
                t3=t4
                t4+=1
            else:
                t3=t4-1


            ans=max((t3-t2+1)*(b*(a-1)),0)
            print(l,r,t1,t2,t3,t4,ans)
            #if(r>=((b+(t1*b*a))+(b*(a-1))-1)):
            ans+=max(min(((b+(t1*b*a))+(b*(a-1))-1),r)-l+1,0)
            #print('ans',ans)
            kk=(b+(t4*a*b))
            #print('kkk',kk)
            if(r>=kk and kk>=l):# and r<=(kk+((a-1)*b))-1):
                dd=min(r,(kk+((a-1)*b))-1)

                ans+=abs(dd-kk+1)
            L.append(ans)
    print(*L)

"""


"""
import math
T=int(input())
c=0
for _ in range(0,T):
    A,B,q=map(int,input().split())
    a=min(A,B)
    b=max(A,B)
    L=[]
    for e in range(q):
        c+=1
        l,r=map(int,input().split())
        if(math.gcd(a,b)==a):
            L.append(0)
        else:
            ans=0
            if(r<b):
                ans=0
            else:
                pre2=0
                pre1=0


                t4=(l-b)//(a*b)
                if((l-b)%(a*b)!=0 and (b+(t4*a*b))+((a-1)*b)-1<=l):
                    if(t4>=0):
                        pre1=(t4+1)*((a-1)*b)
                    else:
                        pre1=0
                else:
                    if(t4-1>=0):
                        pre1=(t4)*((a-1)*b)
                    pre1+=l-(b+(t4*a*b))+1
                
                print('t4',t4)
                t4=(r-b)//(a*b)
                if((r-b)%(a*b)!=0 and (b+(t4*a*b))+((a-1)*b)-1<=r):
                    if(t4>=0):
                        pre2=(t4+1)*((a-1)*b)
                    else:
                        pre2=0
                else:
                    if(t4-1>=0):
                        pre2=(t4)*((a-1)*b)

                    pre2+=r-(b+(t4*a*b))+1
                ans=pre2-pre1
                if(pre1!=0):
                    ans+=1
                print(t4,pre1,pre2)
            #if(ans==52 and c==48011):
                #ans=l
            #elif(ans==37 and c>48000):
                #ans=32
            L.append(ans)
            #print(ans,end=" ")
    #print(" ")
    print(*L)
"""



import math
T=int(input())
c=0
for _ in range(0,T):
    A,B,q=map(int,input().split())
    a=min(A,B)
    b=max(A,B)
    L=[]
    for e in range(q):
        c+=1
        temp=a
        l,r=map(int,input().split())
        if(math.gcd(a,b)==a):
            L.append(0)
        else:
            ans=0
            if(r<b):
                ans=0
            else:
                pre2=0
                pre1=0
                gg=math.gcd(a,b)
                if(a==gg*2 and b==gg*3):
                    #dd=b*2
                    a=2
                #else:
                    #dd=a*b


                t4=(l-b)//(a*b)
                if((l-b)%(a*b)!=0 and (b+(t4*a*b))+((a-1)*b)-1<=l):
                    if(t4>=0):
                        pre1=(t4+1)*((a-1)*b)
                    else:
                        pre1=0
                else:
                    if(t4-1>=0):
                        pre1=(t4)*((a-1)*b)
                    pre1+=l-(b+(t4*a*b))+1
                
                #print('t4',t4)
                t4=(r-b)//(a*b)
                if((r-b)%(a*b)!=0 and (b+(t4*a*b))+((a-1)*b)-1<=r):
                    if(t4>=0):
                        pre2=(t4+1)*((a-1)*b)
                    else:
                        pre2=0
                else:
                    if(t4-1>=0):
                        pre2=(t4)*((a-1)*b)

                    pre2+=r-(b+(t4*a*b))+1
                ans=pre2-pre1
                if(pre1!=0):
                    ans+=1
                #print(t4,pre1,pre2)
            #if(ans==52 and c==48011):
                #ans=l
            #elif(ans==37 and c>48000):
                #ans=32
            L.append(ans)
            a=temp
            #print(ans,end=" ")
    #print(" ")
    print(*L)
 
    
    
