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 \le x \le r_i$, and $((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$. Calculate the answer for each query.

Recall that $y \bmod z$ is the remainder of the division of $y$ by $z$. For example, $5 \bmod 3 = 2$, $7 \bmod 8 = 7$, $9 \bmod 4 = 1$, $9 \bmod 9 = 0$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 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 \le a, b \le 200$; $1 \le q \le 500$).

Then $q$ lines follow, each containing two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 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

Difficulty: interview

Starter code:

Solutions:
t = int(input())
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

for i in range(t):
    a, b, q = map(int, input().split())
    z = gcd(a, b)
    target = (a * b)//z
    pref = [0]
    for j in range(1, target + 1):
        if (j%a)%b != (j%b)%a:
            pref.append(pref[-1]+1)
        else:
            pref.append(pref[-1])
    
    result = []
    for i in range(q):
        l , r = map(int, input().split())
        temp_r = (r//target) * pref[-1]
        r = r%target
        l -= 1
        temp_l = (l//target) * pref[-1]
        l = l%target
        temp_r += pref[r]
        temp_l += pref[l]
        result.append(temp_r - temp_l)
    print(*result)

import sys
input = sys.stdin.readline

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y:
        x, y = y, x % y
    return x

t = int(input())
for _ in range(t):
    a, b, q = map(int, input().split())
    lcm = a * b // gcd(a,b)
    g = gcd(a,b)
    m = max(a,b)

    def f(x):
        total = x // lcm
        extra = x % lcm
        return x - (m * total + min(m,extra))
        
    
    out = [0] * q
    for i in range(q):
        l, r = map(int, input().split())
        out[i] = f(r + 1) - f(l)
        
    print(*out, sep = ' ')


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	a,b,q = map(int,input().split())
	przyg = [0] * (a*b)
	for i in range(a*b):
		if (i%a)%b != (i%b)%a:
			przyg[i] = 1
	cyk = sum(przyg)
	pref = [0]*(a*b)
	pref[0] = przyg[0]
	for i in range(1,a*b):
		pref[i] = pref[i-1] + przyg[i]
	for query in range(q):
		l,r = map(int,input().split())
		ll = l%(a*b)
		rr = r%(a*b)
		wynik = cyk * (r//(a*b) - l//(a*b))
		wynik += pref[rr]
		if ll > 0:
			wynik -= pref[ll-1]
		if query < q-1:
			print(wynik, end = " ")
		else:
			print(wynik)

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


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


def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


t = read_int()
for case_num in range(t):
    a, b, q = read_ints()
    g = gcd(a, b)
    lcm = a * b // g
    acc = [0 for i in range(lcm)]
    for i in range(1, lcm):
        acc[i] = acc[i - 1]
        if (i % a) % b != (i % b) % a:
            acc[i] += 1
    ans = []
    for i in range(q):
        l, r = read_ints()
        curr = 0
        n = l // lcm
        x = l % lcm
        m = r // lcm
        y = r % lcm
        if m > n + 1:
            curr += (m - n - 1) * acc[lcm - 1]
        if m > n:
            curr += acc[lcm - 1] - acc[max(0, x - 1)]
            curr += acc[y]
        if m == n:
            curr += acc[y] - acc[max(0, x - 1)]
        ans.append(curr)
    print(' '.join(map(str, ans)))


import sys
def input():
	return sys.stdin.readline()[:-1]

t = int(input())
for _ in range(t):
	a, b, q = list(map(int, input().split()))
	ans = [0 for _ in range(q)]
	res = [0 for _ in range(a*b)]
	for i in range(1, a*b):
		if (i%a)%b != (i%b)%a:
			res[i] = res[i-1] + 1
		else:
			res[i] = res[i-1]
	def func(x):
		quo, mod = x//(a*b), x%(a*b)
		return quo * res[-1] + res[mod]
	for i in range(q):
		l, r = list(map(int, input().split()))
		ans[i] = func(r) - func(l-1)
	print(*ans)


n_cases = int(input())
for case_num in range(n_cases):
    a, b, q = [int(x) for x in input().split()]
    k = a*b
    pref = [0] * k
    for i in range(1, k):
        pref[i] = pref[i-1]
        if (i % a) % b != (i % b) % a:
            pref[i] += 1
    for i, query in enumerate(range(q)):
        l, r = [int(x) for x in input().split()]
        count = 0
        if l % k != 0:
            count += pref[k-1] - pref[(l % k) - 1]
            l = ((l // k) + 1) * k
        if r % k != k-1:
            count += pref[(r % k)]
            r = (r // k) * k - 1
        assert (r - l + 1) % k == 0
        count += pref[k-1] * ((r - l + 1) // k)
        if i > 0:
            print(' ', end='')
        print(count, end='')
    print()

import sys
readline = sys.stdin.readline

def calc(x):
    D = len(table)
    J = table[-1]
    return x//D*J + table[x%D]

Q = int(readline())
Ans = [None]*Q
for qu in range(Q):
    A, B, T = map(int, readline().split())
    table = [0]*(A*B)
    for i in range(1, A*B):
        if (i%A)%B != (i%B)%A:
            table[i] = 1 + table[i-1]
        else:
            table[i] = table[i-1]
    ans = [None]*T
    for t in range(T):
        l, r = map(int, readline().split())
        l -= 1
        ans[t] = calc(r) - calc(l)
    Ans[qu] = ' '.join(map(str, ans))
print('\n'.join(map(str, Ans)))        

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
# import io, os
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
input = sys.stdin.readline

M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().split()]
def st():return input()
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

def giveab(a,b):
    l = []
    for i in range(1,a * b + 1,1):
        l.append(1 if ((i%a)%b) != ((i%b)%a) else 0)
    return l[:]

def giveforanum(r,s,l):
    temp = r//(a * b)
    up = temp*s
    r %= (a * b)
    
    return up + l[r]


for _ in range(val()):
    a,b,q = li()
    
    l1 = giveab(a,b)
    pref = [0]
    for i in l1:pref.append(pref[-1] + i)

    s = sum(l1)
    ans = []
    for i in range(q):
        l,r = li()
        ans.append(giveforanum(r,s,pref) - giveforanum(l-1,s,pref))
    print(*ans)

from math import gcd

t = int(input())
for __ in range(t):
    a,b,q = list(map(int,input().split()))
    if a > b:
        a, b = b, a
    g = a * b // gcd(a, b)

    # 1以上m以下
    def solve(m):
        if m == 0:
            return 1
        aa,bb = divmod(m + 1, g)
        ret = aa * b
        ret += min(bb, b)
        return ret
    
    def br(l, r):
        ret = 0
        for i in range(l, r + 1):
            if (i % a) % b != (i % b) % a:
                ret += 1
        return ret

    res = []
    # brt = []
    for _ in range(q):
        l,r = list(map(int,input().split()))
        if b % a == 0:
            res.append(0)
        else:
            res.append(r - l + 1 - (solve(r) - solve(l - 1)))
        # brt.append(br(l, r))
    print(*res)
    # print(*brt)


for t in range(int(input())):
    a, b, q = list(map(int, input().split()))
    c = a * b
    x = [0] * (c + 1)
    for i in range(c):
        if (i % a) % b != (i % b) % a:
            x[i] = 1
        x[i] += x[i - 1]

    def get(y):
        if y < 0:
            return 0
        cnt = y // c * x[c - 1]
        return cnt + x[y % c]

    ans = []
    for _ in range(q):
        l, r = list(map(int, input().split()))
        ans.append(get(r) - get(l - 1))
    print(*ans)


from math import gcd

def f(a, b, x):
    x += 1
    p = a * b // gcd(a, b)
    n = x // p
    ans = n * b
    ans += min(b, x - n * p)
    return ans

for _ in range(int(input())):
    a, b, q = map(int, input().split())
    if a > b:
        a, b = b, a
    for i in range(q):
        l, r = map(int, input().split())
        ans = f(a, b, r) - f(a, b, l - 1)
        ans = r - l + 1 - ans
        print(ans, end=' ')
    print()

import sys
input=sys.stdin.readline
def gcd(a,b):
    if a>b:a,b=b,a
    while True:
        a,b=b%a,a
        if a==0:return b
def solve(l,r,a,b,lcm):
    mx=max(a,b)
    d1=l//lcm
    d2=r//lcm
    lr=l%lcm
    rr=r%lcm
    c=0
    if lr>mx:c+=(lcm-lr)
    else:c+=(lcm-mx)
    if rr>=mx:c+=(rr-mx+1)
    c+=(d2-d1-1)*(lcm-mx)
    return c
for i in ' '*int(input()):
    a,b,q=map(int,input().split())
    g=gcd(a,b)
    lcm=a*b//g
    mx=max(a,b)
    for j in ' '*q:
        l,r=map(int,input().split())
        print(solve(l,r,a,b,lcm),end=' ')
    print()


from itertools import accumulate
def solve():
    a, b, q = map(int, input().split())
    tb = [int(i % a % b != i % b % a) for i in range(a * b)]
    bs = sum(tb)
    tb += tb
    tbs = [0] + list(accumulate(tb))
    res = []
    for i in range(q):
        l, r = map(int, input().split())
        r += 1
        w = (r - l) // (a * b)
        ans = w * bs
        r -= w * a * b
        u = l // (a * b)
        l %= a * b
        r -= u * (a * b)
        ans += tbs[r] - tbs[l]
        res.append(ans)
    print(*res)
t = int(input())
for _ in range(t):
    solve()