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:
import sys
from math import log2,floor,ceil,sqrt,gcd
# import bisect
# from collections import deque
sys.setrecursionlimit(7*10**4)

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD =  998244353

def no(n,b,lcm):
    ans = n
    div = n//lcm
    # print(div)
    last = div*lcm
    # ans=  0
    if div != 0 :
        ans -= (div-1)*b
        ans-=(min(n-lcm*div+1,b))
    # print(ans)
    return ans-min(n,b-1)

for _ in range(int(ri())):
    a,b,q  = Ri()
    if a > b:
        a,b = b,a
    for qq in range(q):
        l,r = Ri()
        if l == r:
            if (l%a)%b != (l%b)%a:
                print("1", end = " ")
            else:
                print('0', end = " ")
        elif r < b:
            print("0" , end = " ")
        else:
            if b%a == 0:
                print("0",end = " ")
            else:
                minn = l
                maxx =  r
                lcm = a*b//gcd(a,b)
                # print(lcm)
                left = no(maxx,b,lcm)
                right = no(minn-1,b,lcm)
                # print(right,left)
                cnt = left-right
                print(cnt,end=" ")

    print()