Problem: 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 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  ~debug() { cerr << endl; }
  template <class c>
  typename enable_if<sizeof dud<c>(0) != 1, debug &>::type operator<<(c i) {
    cerr << boolalpha << i;
    return *this;
  }
  template <class c>
  typename enable_if<sizeof dud<c>(0) == 1, debug &>::type operator<<(c i) {
    return *this << range(begin(i), end(i));
  }
  template <class c, class b>
  debug &operator<<(pair<b, c> d) {
    return *this << "(" << d.first << ", " << d.second << ")";
  }
  template <class c>
  debug &operator<<(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it;
    return *this << "]";
  }
};
long long mod = 1000000007;
int INF = 1e9 + 1e8 + 1e7;
long long INF64 = 1e18;
void add(int &a, int &b) {
  a += b;
  if (a > mod) a -= mod;
}
long long binpow(long long a, long long b, long long m) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % m;
    }
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
void test_case(int test) {
  int a, b, q;
  cin >> a >> b >> q;
  vector<int> ca(a * b);
  vector<int> cb(a * b);
  vector<int> pref(a * b + 1);
  for (int i = 0; i < a; i++) {
    ca[i] = i % b;
  }
  for (int i = 0; i < b; i++) {
    cb[i] = i % a;
  }
  for (int i = 0; i < a * b; i++) {
    ca[i] = ca[i % a];
    cb[i] = cb[i % b];
  }
  for (int i = 0; i < a * b; i++) {
    pref[i + 1] = pref[i] + (ca[i] != cb[i]);
  }
  auto get = [&](long long x) {
    long long m = x % (a * b);
    long long d = x / (a * b);
    long long ans = d * pref[a * b];
    if (m != 0) {
      ans += pref[m + 1];
    }
    return ans;
  };
  for (int i = 0; i < q; i++) {
    long long l, r;
    cin >> l >> r;
    cout << (get(r) - get(l - 1)) << ' ';
  }
  cout << '\n';
}
int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  for (int test = 1; test <= t; test++) {
    test_case(test);
  }
  return 0;
}