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 java.util.*;
import java.io.*;
public class codeforces{
    // Input
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader() {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

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

        public String nextLine() {
            String s = null;
            try {
                s = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return s;
        }

        public String nextParagraph() {
            String line = null;
            String ans = "";
            try {
                while ((line = reader.readLine()) != null) {
                    ans += line;
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return ans;
        }
    }
    //Template
    static int mod = 998244353;
    static void printArray(int ar[]){ for(int x:ar) System.out.print(x+" "); System.out.println("---------");}
    static void printArray(ArrayList<Integer> ar){ for(int x:ar) System.out.print(x+" "); System.out.println("---------");}
    static long gcd(long a, long b){ if (a == 0) return b; return gcd(b%a, a);}
    static long power(long x, long y, int p) { long res = 1; x = x % p;  while (y > 0) { if((y & 1)==1) res = (res * x) % p; y = y >> 1;x = (x * x) % p;  } return res;}
    static void takeArrayInput(InputReader sc, int ar[]){ for(int i=0;i<ar.length;i++) ar[i]=sc.nextInt(); }
    static void takeArrayInput(InputReader sc, long ar[]){ for(int i=0;i<ar.length;i++) ar[i]=sc.nextLong(); }
    static void take2dArrayInput(InputReader sc, int ar[][]){ for(int i=0;i<ar.length;i++) for(int j=0;j<ar[i].length;j++) ar[i][j]=sc.nextInt(); }
    static void take2dArrayInput(InputReader sc, long ar[][]){ for(int i=0;i<ar.length;i++) for(int j=0;j<ar[i].length;j++) ar[i][j]=sc.nextLong(); }
    static ArrayList<ArrayList<Integer>> graph(InputReader sc, int n, int m){
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++) list.add(new ArrayList<Integer>());
        for(int i=0;i<m;i++){ int u = sc.nextInt(); int v = sc.nextInt(); list.get(u).add(v); list.get(v).add(u); }
        return list;
    }
    // Write Code Here
    static class Data {
        int u;
        int v;
        public Data(int e, int val) {
            this.u = e;
            this.v = val;
        }
    }
    static void sieveOfEratosthenes(int n, ArrayList<Integer> pr) {
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i < n; i++)
            prime[i] = true;
        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                pr.add(p);
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }
    public static void main(String args[]) {
        InputReader sc = new InputReader();
        PrintWriter pw = new PrintWriter(System.out);
        int i = 0 , j = 0;
        int t = sc.nextInt();
        int alt = 1;
        for (int z = 0 ; z < t;z ++) {
            int a = sc.nextInt(), b = sc.nextInt(), q = sc.nextInt();
            int min = Math.min(a, b), max = Math.max(a, b);
            while (q > 0) {
                long l = Math.max(sc.nextLong(), max), r = sc.nextLong();
                long total = 0;
                long lcm = ((max % min) == 0) ? max : max * min;
                if (r > max) {
                    total += (r-l+1);
                    long lq = l / lcm, rq = r / lcm;
                    if ((r%lcm) < max) {
                        total -= (r%lcm)+1;
                        rq --;
                    }
                    if ((l%lcm) < max) {
                        if ((l%lcm) != 0) {
                            total -= (max -(l%lcm));
                        } 
                    }
                    total -= (rq-lq)*(max);
                }
                pw.print(total + " ");
                q--;
            }
            pw.println();
        }
        pw.close();
    }
}


