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:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
from math import gcd
# sys.setrecursionlimit(100000)
# input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref(A, B, Q):
    L = 0
    for l, r in Q:
        L = max(L, l)
        L = max(L, r)
    s = [0] * (L+1)
    for i in range(len(s)):
        if (i % A) % B != (i % B) % A:
            s[i] = 1

    ans = []
    for l, r in Q:
        ans.append(sum(s[:r+1]) - sum(s[:l]))
    return ans

# @mt
def slv(A, B, Q):
    if max(A, B) % min(A, B) == 0:
        return [0] * len(Q)


    A, B = min(A, B), max(A, B)
    cycle = A * B // gcd(A, B)
    ans = []

    def q(n):
        cn = n // cycle
        r = cn * (cycle - B) + max(0, (n % cycle + 1) - B)
        # error_print(n, r, cn)
        return r

    for l, r in Q:
        ans.append(q(r) - q(l-1))

    return ans



def main():
    T = read_int()
    for _ in range(T):
        A, B, N = read_int_n()
        Q = [read_int_n() for _ in range(N)]
        print(*slv(A, B, Q))
        # print(*ref(A, B, Q))

    # import random
    # A = random.randint(1, 20)
    # B = random.randint(1, 20)
    # Q = []
    # N = 10
    # for _ in range(N):
    #     l = random.randint(1, 100)
    #     r = random.randint(1, 100)
    #     l, r = min(l, r), max(l, r)
    #     Q.append([l, r])
    # print(A, B, N)
    # print(Q)
    # print(*slv(A, B, Q))
    # print(*ref(A, B, Q))


if __name__ == '__main__':
    main()