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>
using namespace std;
void arrange(int &a, int &b) {
  if (b < a) {
    int t;
    t = b;
    b = a;
    a = t;
  }
  return;
}
int hcf(int a, int b) {
  for (int i = a; i >= 1; i--) {
    if (a % i == 0 && b % i == 0) {
      return i;
    }
  }
}
int lcm(int a, int b) { return (a * b) / hcf(a, b); }
void print(vector<long long int> v) {
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
  return;
}
int main(int argc, char const *argv[]) {
  int N;
  cin >> N;
  for (int I = 0; I < N; I++) {
    int a, b, q;
    cin >> a >> b >> q;
    arrange(a, b);
    int g;
    g = lcm(a, b);
    vector<long long int> ans;
    for (int i = 0; i < q; i++) {
      long long int sum = 0, l, r;
      cin >> l >> r;
      long long int t1, t2;
      t1 = l + g - l % g;
      t2 = r - r % g;
      if (t1 <= t2) {
        sum += ((t2 - t1) / g) * (g - b);
        if ((l + g - t1) > b) {
          sum += (t1 - l);
        } else {
          sum += (l - b);
        }
        if ((r - t2) > b) {
          sum += (r - t2 - b + 1);
        }
        ans.push_back(sum);
      } else {
        long long int l1, r1;
        l1 = l % g;
        r1 = r % g;
        if (r1 < b) {
          sum = 0;
        } else {
          if (l1 < b) {
            sum = r1 - b + 1;
          } else {
            sum = r1 - l1 + 1;
          }
        }
        ans.push_back(sum);
      }
    }
    print(ans);
  }
  return 0;
}
