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:
"""
NTC here
"""
 

#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))

def main():
    from math import gcd
    def lcm(a, b):
        return (a*b)//gcd(a, b)
    T = iin()
    while T:
        T-=1
        a, b, q = lin()
        if a>b:a, b= b, a
        lcm1 = lcm(a, b)
        ans = []
        for i in range(q):
            sol = 0
            l, r = lin()
            l1 = l
            r1 = r
            sol += max(min(r, b-1)-l+1, 0)
            # print('s1-', sol)
            l = max(lcm1, l)
            if l<=r:
                x1 = (r)//lcm1-(l-1)//lcm1
                # print(l, r, lcm1)
                sol += x1*b
                x2 = (r//lcm1)*lcm1
                if x1 and x2+b>r:
                    sol -= b
                    sol += min(r-x2+1, b)
                    # print('i1-', min(r-x2+1, b))
                x2 = ((l-1)//lcm1)*lcm1
                if x2+b>l:
                    sol += min(x2+b-1, r)-l+1
                    # print('i2-', x2, l, min(x2+b-1, r)-l+1)
            # print('s2-', sol)
            ans.append(r1-l1+1-sol)
        print(*ans)
        





# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()