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;
int main() {
  int t;
  int a, b, q;
  long long ans;
  long long l;
  long long r;
  long long start;
  scanf("%d", &t);
  while (t--) {
    ans = 0;
    scanf("%d %d %d", &a, &b, &q);
    if (a > b) swap(a, b);
    start = a * b;
    for (int i = 0; i < q; i++) {
      ans = 0;
      scanf("%lld %lld", &l, &r);
      if (r < b || b % a == 0) {
        printf("0 ");
      } else if (r == b) {
        if (r % a != 0)
          printf("1 ");
        else
          printf("0 ");
      } else if (r < start) {
        printf("%lld ", r - b + 1);
      } else if (r > start) {
        ans += (r / start - 1) * b;
        if (r % start < b)
          ans += r % start + 1;
        else
          ans += b;
        if (l > start) {
          ans -= (l / start - 1) * b;
          if (l % start < b)
            ans -= l % start + 1;
          else
            ans -= b;
        }
        ans = r - l + 1 - ans;
        printf("%lld ", ans);
      }
    }
    printf("\n");
  }
}
