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 
// Jai Shri Ram
import javax.management.DynamicMBean;
import javax.print.DocFlavor;
import javax.print.attribute.HashAttributeSet;
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.net.Inet4Address;
import java.nio.file.attribute.FileAttribute;
import java.sql.SQLType;
import java.time.DayOfWeek;
import java.time.LocalDate;
import java.time.Month;
import java.time.temporal.TemporalAdjusters;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;
import java.util.Arrays;
import java.util.concurrent.Callable;
import java.time.DayOfWeek;
import java.time.LocalDate;
import java.time.Month;
import java.time.temporal.TemporalAdjusters;



public class Main {
    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;
        }
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
       int t=sc.nextInt();
       for(int i=0;i<t;i++){
          int a=sc.nextInt();
          int b=sc.nextInt();int q=sc.nextInt();
          for(int j=0;j<q;j++){
              long l=sc.nextLong();
              long r=sc.nextLong();
              if(r<Math.max(b,a)){
                  System.out.print(0+" ");
              }
              else{
                  long count=0;
                  long m=Math.max(Math.max(b,a),l);
//                  for(long m=Math.max(b,l);m<=r;m++){
//                        if((m%a)%b!=(m%b)%a){
//                            count++;
//                        }
//                  }
                  long p=m;
                  long s=r;
                  int lc=lcm(a,b);
                  if(r<lc){
                      count=r-m+1;
                  }
                  else{
                      long v=m%lc;
                      m+=lc-v;
                      long vv=r%lc;
                      r-=vv;
                      long val=(r-m)/lc;
                      val++;
                      long w=(val-1)*(Math.max(b,a)-1);
                      w+=Math.min(vv,(Math.max(b,a)-1));
                       count=(s-p+1)-val-w;
                  }
                  System.out.print(count+" ");
              }

          }
           System.out.println(" ");
       }



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

    // method to return LCM of two numbers
    static int lcm(int a, int b)
    {
        return (a*b)/gcd(a, b);
    }



}