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 int             long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define sz(x)           (int)(x.size())
#define all(x)          x.begin(),x.end()
#define repf(i,s,e)     for(int i=s;i<e;i++)
#define AUTO(c,v)         for(auto c:v) 

template<typename T,typename T1>T smax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T smin(T &a,T1 b){if(b<a)a=b;return a;}

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define nl '\n'
template <typename T, size_t N>
 int SIZE(const T (&t)[N]){
     return N;
 }

 template<typename T>
 int SIZE(const T &t){
     return t.size();
 }

 string to_string(const string s, int x1=0, int x2=1e9){
     return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"';
 }

 string to_string(const char* s) {
     return to_string((string) s);
 }

 string to_string(const bool b) {
     return (b ? "true" : "false");
 }

 string to_string(const char c){
     return string({c});
 }

 template<size_t N>
 string to_string(const bitset<N> &b, int x1=0, int x2=1e9){
     string t = "";
     for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){
       t += b[__iii__] + '0';
     }
     return '"' + t + '"';
 }

 template <typename A, typename... C>
 string to_string(const A (&v), int x1=0, int x2=1e9, C... coords);

 int l_v_l_v_l = 0, t_a_b_s = 0;

 template <typename A, typename B>
 string to_string(const pair<A, B> &p) {
     l_v_l_v_l++;
     string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
     l_v_l_v_l--;
     return res;
 }

 template <typename A, typename... C>
 string to_string(const A (&v), int x1, int x2, C... coords) {
     int rnk = rank<A>::value;
     string tab(t_a_b_s, ' ');
     string res = "";
     bool first = true;
     if(l_v_l_v_l == 0) res += nl;
     res += tab + "[";
     x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v));
     auto l = begin(v);
     advance(l, x1);
     auto r = l;
     advance(r, (x2-x1) + (x2 < SIZE(v)));
     for (auto e = l; e != r; e = next(e)) {
         if (!first) {
             res += ", ";
         }
         first = false;
         l_v_l_v_l++;
         if(e != l){
             if(rnk > 1) {
                 res += nl;
                 t_a_b_s = l_v_l_v_l;
             };
         }
         else{
             t_a_b_s = 0;
         }
         res += to_string(*e, coords...);
         l_v_l_v_l--;
     }
     res += "]";
     if(l_v_l_v_l == 0) res += nl;
     return res;
 }

 void dbg(){;}
 template<typename Heads, typename... Tails>
 void dbg(Heads H, Tails... T){
     cout << to_string(H) << " | ";
     dbg(T...);
}
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbg(__VA_ARGS__); cout << endl;

/* read */
template<typename... T>
void read(T&...args){
    ((cin>>args),...);
}
template<class T>
void readArray(vector<T>& arr){
    for(auto& c:arr) cin>>c;
}
/* print */
template<typename...T>
void print(T...args){
    ((cout<<args<<" "),...);
}
template<class T>
void printArray(vector<T>& arr){
    AUTO(c,arr) cout<<c<<" ";
    nl;
}

const int INF=1e18;

void solve() {
    int a,b,q;
    read(a,b,q);
    if(a<b) swap(a,b);
    int lcm=(a*b)/(__gcd(a,b));
    vector<int> poss(a,1);
    while(q--){
        int l,r;
        read(l,r);
        int ans=r-l+1; // number of equal
        int lower=l,upper=r;
        while(lower<=upper && (lower%lcm)>0){
            if((lower%lcm)<a) ans--;
            lower++;
        }
        // if(lower<=upper && (lower%lcm)==0) ans--;
        while(upper>lower && (upper%lcm)>0){
            if((upper%lcm)<a && upper<=r) ans--;
            upper++;
        }
        int A=lower/lcm;
        int B=upper/lcm;
        ans-=((B-A)*(a));
        cout<<ans<<" ";
    }    
    cout<<nl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // if(fopen("input.txt", "r")){
    //     freopen("input.txt", "r", stdin),
    //     freopen("output.txt", "w", stdout);
    // }
    
    int t = 1;
    cin>>t;
    for(int i=1;i<=t;i++) {
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}