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:
from math import *

for zz in range(int(input())):
    a, b, q = map(int, input().split())
    x = max(a, b)
    y = min(a, b)
    a = x
    b = y
    #print(a, b)
    if a == b:
        for i in range(q):
            input()
        print('0 ' * q)
    else:
        res = []
        for xx in range(q):
        #for l in range(1, 100):
            #for r in range(l, 101):
            #print(l, r)
            l, r = map(int, input().split())
            ans = r - l + 1
            cb = (a * b)//gcd(a,b)
            lb = l // cb
            if l % cb > 0:
                lb += 1
            ub = (r - a + 1) // cb
            #print(cb, lb, ub)
            #print(ans)
            ans -= a * max(0, (ub - lb + 1))
            #print(ans, (ub + 1) * cb, min(r, (ub + 1)*cb + a - 1))
            ans -= max(0, (lb - 1)*cb + a - 1 - max((lb - 1) * cb, l) + 1)
            if (ub - lb) > -2: 
                ans -= max(0, min(r, (ub + 1)*cb + a - 1) - (ub + 1) * cb + 1)
            x = max(ans, 0)
            #x2 = 0
            #for i in range(l, r + 1):
            #    if ((i % a) % b) != ((i % b) % a):
            #        x2 += 1
            #if (x != x2):
            #    print(l, r, x, x2)
            res.append(x)
                #res.append(ans)
        print(*res)