C. Yet Another Counting Problem

You are given two integers aa and bb, and qq queries. The ii-th query consists of two numbers lili and riri, and the answer to it is the number of integers xx such that li≤x≤rili≤x≤ri, and ((xmoda)modb)≠((xmodb)moda)((xmoda)modb)≠((xmodb)moda). Calculate the answer for each query.

Recall that ymodzymodz is the remainder of the division of yy by zz. For example, 5mod3=25mod3=2, 7mod8=77mod8=7, 9mod4=19mod4=1, 9mod9=09mod9=0.

Input

The first line contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases. Then the test cases follow.

The first line of each test case contains three integers aa, bb and qq (1≤a,b≤2001≤a,b≤200; 1≤q≤5001≤q≤500).

Then qq lines follow, each containing two integers lili and riri (1≤li≤ri≤10181≤li≤ri≤1018) for the corresponding query.

Output

For each test case, print qq integers — the answers to the queries of this test case in the order they appear.

Example

input

Copy

2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200

output

Copy

0 0 0 2 4 
0 91 

 在这个问题里面，（r-l+1）/LCM和r/LCM-（l-1）/LCM差别是很大的。。。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>
//#include <xfunctional>
#define ll              long long
#define PII             pair<int, int>
#define rep(i,a,b)      for(int  i=a;i<=b;i++)
#define dec(i,a,b)      for(int  i=a;i>=b;i--)
#define pb              push_back
#define mk              make_pair
using namespace std;
int dir[4][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979;
const int mod = 998244353;
const int N = 1e6+5;
//if(x<0 || x>=r || y<0 || y>=c)

inline ll read()
{
    ll x = 0; bool f = true; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = false; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? x : -x;
}
ll gcd(ll m, ll n)
{
    return n == 0 ? m : gcd(n, m % n);
}
ll lcm(ll m, ll n)
{
    return m*n / gcd(m, n);
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        ll a, b, q;
        cin >> a >> b >> q;
        ll LCM = lcm(a, b);
        vector<ll> v(LCM+1,0);
        for (int i = 1; i <= LCM; i++)
        {
            if ((i%a)%b != (i%b)%a)
            {
                v[i] = v[i - 1] + 1;
            }
            else
                v[i] = v[i - 1];
        }

        while (q--)
        {
            ll l, r;
            l = read(), r = read();
            ll t1 = r/LCM*v[LCM]+v[r%LCM];
            ll t2 = (l - 1) / LCM*v[LCM] + v[(l - 1) % LCM];
            cout << t1 - t2<< " ";
        }
        cout << endl;
    }
    return 0;
}