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 
from math import gcd
from math import ceil,floor
from sys import stdin
inp = stdin.readline

t = int(inp().strip())


def lcm(a,b):
    return (a*b) / gcd(a,b)


for _ in range(t):
    a, b, q = [int(x) for x in inp().strip().split()]
    maximum = max(a,b)
    ans = []
    for _2 in range(q):
        l, r = [int(x) for x in inp().strip().split()]
        lc = lcm(a, b)
        maxLC = floor(r / lc)
        minLC = ceil(l/lc)
        if l % lc == 0:
            minLC = ceil((l+1)/lc)
        if r % lc == 0 and l != r:
            maxLC = floor((r-1) / lc)
        ans1 = (r-l+1) - (maxLC-minLC + 1)*maximum
        index1 = 0
        reached = 0
        while True:
            if l + index1 > r or index1 >= maximum:
                break
            if ((l + index1)%a)%b == ((l + index1)%b)%a:
                ans1 -= 1
            else:
                break
            index1 += 1
            reached = l + index1
        index1 = 0
        while True:
            if r-index1 < reached or index1 >= maximum:
                break
            if ((r - index1) % a) % b == ((r - index1) % b) % a:
                ans1 -= 1
            else:
                break
            index1 += 1
        ans.append(int(max(ans1,0)))
    print(*ans)
