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 

import com.sun.org.apache.bcel.internal.generic.ALOAD;
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import javafx.util.Pair;
import jdk.nashorn.internal.ir.BreakNode;
public class Fff {

   static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static   StringBuilder out=new StringBuilder();
 static  BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
 static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static int I(String s) {return Integer.parseInt(s);}
    static long L(String s) {return Long.parseLong(s);}
    static double D(String s) {return Double.parseDouble(s);}
     static String[] SA() throws IOException {return bf.readLine().split(" ");}
    
    public static void main(String[] args) throws IOException {

   
   
       int t=I(bf.readLine());
      while(t-->0){
             StringTokenizer in = new StringTokenizer(bf.readLine());
             int a=I((String)in.nextElement());
              int b=I((String)in.nextElement());
            int max =Math.max(a, b);
            int min=Math.min(a, b);
             int q=I((String)in.nextElement());
              
               long count=0;
        for(int i=0;i<q;i++){ in = new StringTokenizer(bf.readLine());
            long te1=L((String)in.nextElement());
            long te2=L((String)in.nextElement());
            long s=Math.max(te1, max);
            long f=te2;
            long myl=a*b;
           long m=  (long)Math.ceil((double)s/myl);
           long mm= (long)Math.ceil((double)f/myl);
           BigInteger bg=new BigInteger((mm-m)+"");
           BigInteger ma=new BigInteger((max)+"");
             BigInteger ff=new BigInteger(f+"");
             BigInteger ss=new BigInteger(s+"");
           bg=bg.multiply(ma);
           bg=ff.subtract(ss).subtract(bg).add(BigInteger.ONE);
         
            long z=(long)((long)(mm-m)*(long)max);
           
            if(f-s>0){  out.append(bg+" ");}
            else{out.append("0 ");}
          
        }
        out.append("\n");
      }System.out.print(out);
   
    }
}
