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 
//--------------------------------------------------------------------------------
// Code By:
//					######                  #               ######
//					##   #                  #               #
//					#####      ##       #####      ##       #   ###
//					##   #              #   #               #   # #
//					##    #	            #####               ##### #
//---------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;

                             /* ----------------------------- START of Template ---------------*/
#define ll long long int
#define FOR(x,to) for(x=0;x<(to);x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define repd(i,a,b) for(ll i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define vvll vector<vector<long long int> >
#define vll vector<long long int>
#define MINUS(a) memset(a,0xff,sizeof(a))
#define SZ(X) ((int)(X).size())
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
vector<ll>isprime;
void seive(ll size){
	isprime.resize(size+1,1);
	ll i,j;
	isprime[0]=0;
	isprime[1]=0;
	for(i=2;i*i<=size;i++){
		if(isprime[i]){
			for(j=2;j*i<=size;j++)isprime[i*j]=0;
		}
	}
}
ll power(ll x,unsigned ll y, ll m){
	if(y==0)return 1;
	ll p=power(x,y/2,m);
	p=(p*p)%m;
	if(y%2!=0)p=(p*x)%m;
	return p;
}
ll modinverse(ll a,ll m){
	return power(a,m-2,m);
}
                       /* ----------------------          End Of Template --------------------------------*/

ll findans(){
  ll a,b,q,x,y,i;
  cin>>a>>b>>q;
  ll m=(a*b)/__gcd(a,b);
  while(q--){
  	cin>>x>>y;
  	ll fm=x/m;
//  	cout<<"-------------"<<endl;
  	if(x%m!=0)fm++;
  	ll lm=y/m;
  	ll cnt=0;
  	for(i=1;i<max(a,b);i++){
		if(i>=x&&i<=y)cnt++;
	}
//  	cout<<fm<<" "<<lm<<"fm lm";
if(lm!=0)
  	for(i=m*lm;i<=(m*lm)+max(a,b);i++){
  		if(i>=x&&i<=y)cnt++;
	  }
//	  cout<<cnt;
	  if(lm>fm)
	  cnt+=(lm-fm)*max(a,b);

	cout<<(y-x+1)-cnt<<" ";
//	cout<<"\n-----------"<<endl;
  }
  cout<<endl;
  return 0;



}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll t,i;
	cin>>t;
	for(i=0;i<t;i++){
		findans();
	}
return 0;
}

