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:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College
    Date:26/04/2020

'''
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())


abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def powmod(a,b):
    a%=mod
    if(a==0):
        return 0
    res=1
    while(b>0):
        if(b&1):
            res=(res*a)%mod
        a=(a*a)%mod
        b>>=1
    return res




def func(x,y,c):
    c1=x//y
    ans=(c1*c)
    x%=y
    x+=1
    if(x<c):
        ans+=(x-c)
    # print(ans)
    return ans
    
    
    
def main():
    
    for _ in range(ii()):
        a,b,q=mi()
        if(b>a):
            a,b=b,a
        x=a
        y=(a*b)//gcd(a,b)
        for i in range(q):
            l,r=mi()
            l-=1
            if(a==b or r<a):
                print('0',end=" ")
                continue
            if(r>=y):
                ans=r-func(r,y,x)-a+1
            else:
                ans=(r-a+1)
            if(l>=y):
                ans1=l-func(l,y,x)-a+1
            else:
                if(l<a):
                    ans1=0
                else:
                    ans1=(l-a+1)
            # print(ans,ans1)
            print(ans-ans1,end=" ")
        print()














if __name__ == "__main__":
    main()