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 JAVA):

Solution:
/*
 *created by Kraken on 27-04-2020 at 02:11
 */
//package com.kraken.cf.practice;

import java.util.*;
import java.io.*;

public class C1342 {

  public static void main(String[] args) {
    FastReader sc = new FastReader();
    int tt = sc.nextInt();
    StringBuilder sb = new StringBuilder();
    while (tt-- > 0) {
      int a = sc.nextInt(), b = sc.nextInt(), q = sc.nextInt();
      if (a > b) {
        a += b;
        b = a - b;
        a -= b;
      }
      long lcm = (a * b) / gcd(a, b);
      long res, bad;
      while (q-- > 0) {
        long l = sc.nextLong(), r = sc.nextLong();
        if (lcm == b) {
          sb.append("0 ");
          continue;
        }
        res = r - l + 1;
        bad = 0;
//        long cnt = (l / lcm) * lcm;
//        if (cnt + b >= l) {
//          bad += cnt + b - l;
//          l = cnt + b;
//        }
//        cnt = (r / lcm) * lcm;
//        if (cnt + b >= r) {
//          bad += r - cnt + 1;
//          r = cnt - 1;
//        }
        while (l <= r && l % lcm < b) {
          bad++; l++;
        }
        while (r >= l && r % lcm < b) {
          bad++; r--;
        }
        long l1 = l / lcm + 1;
        long r1 = r / lcm;
        bad += (r1 - l1 + 1) * b;
        sb.append(Math.max(0, res - bad) + " ");
      }
      sb.append("\n");
    }
    System.out.print(sb);
  }

  private static long gcd(int a, int b) {
    if (a == 0) return b;
    return gcd(b % a, a);
  }

  static class FastReader {

    BufferedReader br;

    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        }
        catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      }
      catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }
}