Yet Another Counting Problem CodeForces

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

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 <iostream>
//#include <cstdio>
//#include <cmath>
//#include<cstring>
//#include <algorithm>
//#include <queue>
//#include<map>
//#include<set>
//#include<vector>
using namespace std;
typedef long long ll;
const int inf = 1e9;
const int mod = 998244353;
const int mx = 1e7; //check the limits, dummy
typedef pair<int, int> pa;
const double PI = acos(-1);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
#define swa(a,b) a^=b^=a^=b
#define re(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define rb(i,a,b) for(int i=(a),_=(b);i>=_;i--)
#define clr(a) memset(a, 1, sizeof(a))
#define lowbit(x) ((x)&(x-1))
#define mkp make_pai
void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); }
int n, m, k,t;
char s[mx];
ll dp[mx];
ll x, y,a,b,q;
int f[mx];
ll solve(long long p, int n) {
    return f[n - 1] * (p / n) + f[p % n];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    scanf("%d", &t);
    while (t--) {
        int a, b, q;
        scanf("%d %d %d", &a, &b, &q);
        int n = a * b;
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1];
            if (i % a % b != i % b % a)
                f[i] ++;
        }
        while (q--) {
            ll l, r;
            scanf("%lld %lld", &l, &r);
            printf("%lld ", solve(r, n) - solve(l - 1, n));
        }
        puts("");
    }
    return 0;
}