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>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define F              first
#define S              second
#define int             long long int
#define ll              int
#define pb              push_back
#define mp              make_pair
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define MODULO(a,b) ((a>=0)?(a%b):((b+a)%b))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*NcR*/
int NcR(int n, int r)
{
    int p = 1, k = 1;
    if (n - r < r)
        r = n - r;
    if (r != 0) {
        while (r) {
            p *= n;k *= r;
            int m = __gcd(p, k);
            p /= m;k /= m;
            n--;r--;
        }
    }
    else{
        p = 1;
    }
        return p;

}
/*NcR*/
/*Fibonacci Series*/
map<int, int> fib;
int f(int n) {//n>=2 && n->0-indexed
	if (fib.count(n)) return fib[n];
	int k=n/2;
	if (n%2==0) { // n=2*k
		return fib[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % mod;
	} else { // n=2*k+1
		return fib[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % mod;
	}
}
/*Fibonacci Series*/

int toInt(string s){
    stringstream obj(s);
    int x=0;
    obj>>x;
    return x;
}
/*Sieve Of Eratosthenes*/
const int NN=1000000;
bool prime[NN+1];
vi primes_v;
void SieveOfEratosthenes(){
memset(prime,true,sizeof(prime));
for(int p=2;p*p<=NN;p++){//or p<=N;
    if(prime[p]==true){
        for(int i=p*p;i<=NN;i+=p)
        prime[i]=false;
    }
}
}
/*Sieve Of Eratosthenes*/
/*Reserved Variable
NN,fib,prime,toInt,f,NcR,primes_v
*/
/*********************************************************************************************************************************/

void solve()
{
    //SieveOfEratosthenes();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	w(t){
		int a,b,q;
		cin>>a>>b>>q;
		int l=a*b;
		int ar[l]={0};
		ar[0]=0;
		for(int i=1;i<l;i++)
		{
			if(((i%a)%b)!=((i%b)%a))
			ar[i]=1;
		}
		int p_sm[l]={0};
		for(int i=1;i<l;i++){
			p_sm[i]=ar[i]+p_sm[i-1];
		}
		int L,R;
		//fo(i,l)
	//	cout<<ar[i]<<" ";
		while(q--){
			cin>>L>>R;
			int ans=0;
			int cycles=(R-L+1)/(l);
			int rem=(R-L+1)%(a*b);
			int val=p_sm[l-1];
			ans+=cycles*(val);
			int start=L%l;
			int end=R%l;
			if(start>end){
				ans+=(p_sm[l-1]-p_sm[start-1]+p_sm[end]);
			}
			else if(end>start){
				ans+=p_sm[end];
				if(start!=0)
				ans-=p_sm[start-1];
			}
			else
			ans+=ar[start];

			cout<<ans<<" ";
		}
		cout<<"\n";
	}

}

int32_t main()
{
	solve();
	return 0;
}