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:
import java.io.*;
import java.util.*;


public class c{

    public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));

      int t = sc.nextInt();
      for(int i=0; i<t; i++) {
          int a = sc.nextInt();
          int b = sc.nextInt();
          int q = sc.nextInt();
          int temp_min = Math.min(a,b);
          a = Math.max(a,b);
          b = temp_min;
          int gcd = 1;
          for(int j=1; j<=b; j++) {
              if(a%j==0 && b%j==0) {
                  gcd = j;
              }
          }
          int lcm = a*b/gcd;
          int modulus = b/gcd;
          for(int j=0; j<q; j++) {
              long l = sc.nextLong();
              long r = sc.nextLong();
              long extrarounds = (r-l) / lcm;
              long totalcount = extrarounds * (lcm-a);
              r -= extrarounds * lcm;
              long lowerfloor = l/a;
              long upperfloor = r/a;
              long lowercount = a - l%a;
              long uppercount = r%a + 1;
              if(lowerfloor == upperfloor) {
                  if(lowerfloor%modulus != 0) {
                      totalcount += (r-l+1);
                  }
              } else {
                  if(lowerfloor%modulus != 0) {
                      totalcount += lowercount;
                  }
                  if(upperfloor%modulus != 0) {
                      totalcount += uppercount;
                  }
                  for(long k=lowerfloor + 1; k < upperfloor; k++) {
                      if(k%modulus != 0) {
                          totalcount += a;
                      }
                  }
              }
              out.println(totalcount);
          }
      }




      
      
      

      // Start writing your solution here. -------------------------------------
   
      /*
      int n      = sc.nextInt();        // read input as integer
      long k     = sc.nextLong();       // read input as long
      double d   = sc.nextDouble();     // read input as double
      String str = sc.next();           // read input as String
      String s   = sc.nextLine();       // read whole line as String

      int result = 3*n;
      out.println(result);                    // print via PrintWriter
      */

      // Stop writing your solution here. -------------------------------------
      out.close();
   }

   public static int match(char[] a, char[] b) {
      int count = 0;
      for(int i =0; i<a.length; i++) {
          if(a[i]==b[i]) {
              count++;
          }
      }
      return a.length-count;
   }

   static  class pair{
    int u;
    int v;
    int w;
    int x;
    pair(int u, int v, int w, int x) {
        this.u=u;
        this.v=v;
        this.w=w;
        this.x=x;
    }
    
}

static class sortbyarr implements Comparator<pair> 
{ 
    // Used for sorting in ascending order of 
    // roll number 
    public int compare(pair a, pair b) 
    { 
        return a.u - b.u; 
    } 
}

static class sortbyi implements Comparator<pair> 
{ 
    // Used for sorting in ascending order of 
    // roll number 
    public int compare(pair a, pair b) 
    { 
        return a.x - b.x; 
    } 
}

   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         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;
      }

   }
   //--------------------------------------------------------
}