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 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define d long double

#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define dscf(n) scanf("%Lf",&n)
#define pri(n) printf("%d ",(int)n)
#define lpri(n) printf("%lld ",n)
#define dpri(n) printf("%Lf ",n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define dprin(n) printf("%Lf\n",n)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,ini,n) for(ll i=ini;i<(int)n;i++)
#define all(x) x.begin(),x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define bitcount(n) __builtin_popcount(n)
#define tc   int tt; scf(tt); while(tt--)
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265358979323846264

const ll M =1e9+7;
const int N = 1e6+7;

ll lcm(ll a,ll b)
{
    return (a*b)/gcd(a,b);
}

int main()
{
    tc{
        ll a,b,n,m,q;

        lscf(n), lscf(m), lscf(q);

        a=min(n,m);
        b=max(n,m);

        ll lc=lcm(a,b);

        ll res=0;

        rep(i,lc,2*lc)
        if((i%a)%b!=(i%b)%a)
        res++;

        while(q--)
        {
            ll l,r;
            lscf(l),lscf(r);

            if(r<=a)
            {
                printf("0 ");
            }
            else
            { 
                
                ll low=l/lc;
                ll high=r/lc;

                ll ans=(high-low)*res;

                low=low*lc;
                high=high*lc;

                rep(i,low,l)
                if((i%a)%b!=(i%b)%a)
                ans--;

                rep(i,high,r+1)
                if((i%a)%b!=(i%b)%a)
                ans++;

                lpri(ans);
            }
            
        }

        printf("\n");
    }
return 0;
}