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>
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define INF 1e18
#define ft first
#define sc second
#define pb push_back
#define mpr make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define booost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
#define all(x) (x).begin(),(x).end()
#define allo(x, n) (x),(x) + (n)
#define file(x) freopen(string(string((x)) + ".in").c_str(), "r", stdin); freopen(string(string((x)) + ".out").c_str(), "w", stdout);
#define GG cout << " OPA " << '\n';

using namespace std;
using namespace __gnu_pbds;

typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair <int, int> pi;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e2 + 5;

main()
{
    int t;
    cin >> t;
    while (t --)
    {
        int a, b, q;
        cin >> a >> b >> q;
        int dp[a * b + 1];
        int cur = a * b;
        for (int i = 0; i <= a * b + 1; i ++)dp[i] = 0;
        dp[0] = 1;
        for (int i = 1; i < a * b; i ++)
        {
            if ((i % a) % b == (i % b) % a)dp[i] = dp[i - 1] + 1;
            else dp[i] = dp[i - 1];
                //dp[i] = (i?dp[i - 1]:0) + ((i % a) % b == (i % b) % a ? 1 : 0);
        }
        while (q --)
        {
            int l, r;
            cin >> l >> r;
            if (l / (a * b) == r / (a * b))
            {
                cout << r - l + 1 - (dp[r % cur] - (l % cur ? dp[l % cur - 1] : 0)) << ' ';
                //if (l % cur == 0)cout << r - l + 1 - dp[r % cur] << ' ';
                //if (l % cur != 0)cout << r - l + 1 - dp[r % cur] + dp[l % cur - 1] << ' ';
            }
            else
            {
                //cout << r - l + 1 - (dp[cur - 1] - (l % cur ? dp[l % cur - 1] : 0) + dp[r % cur] + max(0ll, (r / cur - l / cur - 1)) * dp[cur - 1]) << ' ';
                if (l % cur == 0)cout << r - l + 1 - dp[cur - 1] + dp[r % cur] + max(0ll, (r / cur - l / cur - 1)) * dp[cur - 1] << ' ';
                if (l % cur != 0)cout << r - l + 1 - dp[cur - 1] - dp[l % cur - 1] + dp[r % cur] + max(0ll, (r / cur - l / cur - 1)) * dp[cur - 1] << ' ';
            }
        }
        cout << '\n';
    }
}
