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 
// Reading stuff 
// check the modulus 
// for tree case n=1

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
 
#include <bits/stdc++.h>
#include <vector> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

#define int         long long
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define mp          make_pair
#define all(a)      (a).begin(),(a).end()
#define FF           first
#define SS           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
const ll hell=1000000007;
const ll mod=1000000007;



int solve(){    


 int a,b,q;
 cin>>a>>b>>q;

 int x=a*b+1;
 int aa[x],bb[x],cnt=0;
 rep(i,1,x)
 {
  aa[i]=(i%a)%b;
  bb[i]=(i%b)%a;
  if(aa[i]==bb[i])cnt++;
 }
  
  rep(i,0,q)
  {
    int l,r;
    cin>>l>>r;
  int ans1=(l-1),ans2=r;
  ans1/=(x-1);
  ans2/=(x-1);
  ans1*=cnt;
  ans2*=cnt;
  
int k=l-1,kk=r;
k%=x;
kk%=x;

rep(i,1,k+1)if(aa[i]==bb[i])ans1++;
rep(i,1,kk+1)if(aa[i]==bb[i])ans2++;
 int res=r-l+1;
 res-=ans2;
 res+=ans1;
cout<<res<<" ";
}
cout<<endl;

return 0;
}

 
signed main()
{    

     #ifndef ONLINE_JUDGE
       freopen("input.txt", "r" , stdin);
       freopen("output.txt", "w", stdout);                                  
      #endif  

   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0); 

int t=1;                                                                                                                  
cin>>t;
int k=1;

    while(t--)
     {
      //cout<<"Case #"<<k<<": ";
      k++;
      solve();
     }
    return 0;
  }