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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    static long MOD = 0;
    static long[] fact = new long[1];

    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        int t = in.nextInt();
        while (t-- > 0) {
            //15 37 2 7
            //6 50 2 3
           // solve_cmp(2, 3, 6, 50);
            //3 50 2 3
            //solve_cmp(2, 3, 3, 50);
            solve();
        }
        long endTime = System.nanoTime();
        err.println("Execution Time : +" + (endTime - startTime) / 1000000 + " ms");
        exit(0);
    }

    static void solve_n() {
        for (int i = 1; i <= 50; i++) {
            for (int j = i; j <= 50; j++) {
                for (int k = 1; k <= 50; k++) {
                    for (int l = k; l <= 50; l++) {
                        solve_cmp(i, j, k, l);
                    }
                }
            }
        }
    }

    static void solve() {
        int a = in.nextInt();
        int b = in.nextInt();
        if (a > b) {
            int temp = b;
            b = a;
            a = temp;
        }
        int q = in.nextInt();
        while (q-- > 0) {
            long l = in.nextLong();
            long r = in.nextLong();
            if (r < l) {
                long temp = r;
                r = l;
                l = temp;
            }
            long ans = r - l + 1;
            if (l < b) {
                ans -= b - l;
            }
            if (a % b == 0 || b % a == 0 || ans <= 0) {
                out.print(0);
                out.print(' ');
            } else {
                long l_count = count(l-1, a, b);
                long r_count = count(r , a, b);
                long diff = r_count - l_count ;
                ans -= diff;
                out.print(ans);
                out.print(' ');
                //                if (ans != bf(l, r, a, b)) {
                //                    out.println(ans + " " + l + " " + r + " " + a + " " + b + " " + bf(l, r, a, b));
                //                }
            }
        }
        out.println("");
    }

    //GCD Long
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static void solve_cmp(int a, int b, long l, long r) {
        if (a > b) {
            int temp = b;
            b = a;
            a = temp;
        }

        if (r < l) {
            long temp = r;
            r = l;
            l = temp;
        }
        long ans = r - l + 1;
        if (l < b) {
            ans -= b - l;
        }
        if (a % b == 0 || b % a == 0 || ans <= 0) {
            ans = 0;
            if (ans != bf(l, r, a, b)) {
                out.println(ans + " " + l + " " + r + " " + a + " " + b + " " + bf(l, r, a, b));
            }
        } else {
            long l_count = count(l-1, a, b);
            long r_count = count(r , a, b);
            //out.println(l_count + " COUNTS " + r_count + " " + ans);
            long diff = r_count - l_count;
            ans -= diff;
            if (ans != bf(l, r, a, b)) {
                out.println(ans + " " + l + " " + r + " " + a + " " + b + " " + bf(l, r, a, b));
            }
        }

    }

    static long count(long n, long a, long b) {
        long x = a * b;
        if (gcd(a, b) != 1) {
            x /= gcd(a, b);
        }
        long mul = n / x;
        if (mul == 0) {
            return 0;
        } else {
            // out.println( n + " " + x + "   " + mul + " MUL " );
            if (mul * x + b - 1 <= n) {
                return mul * b;
            }
            int count = 0;
            for (long i = b; i >= 1; i--) {
                if (mul * x + b - i <= n) {
                    count++;
                } else {
                    break;
                }
            }
          //  out.println( n + " " + x + "   " + mul + " MUL " + count);
            mul--;
            return mul * b + count;
        }
    }

    static int bf(long l, long r, int a, int b) {
        int ans = 0;
        for (long i = l; i <= r; i++) {
            if ((i % a) % b != (i % b) % a) {
              //  out.println(i);
                ans++;
            }
        }
        return ans;
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            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 long nextLong() {
            return Long.parseLong(next());
        }

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

        public int[] readAllInts(int n) {
            int[] p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = in.nextInt();
            }
            return p;
        }

        public int[] readAllInts(int n, int s) {
            int[] p = new int[n + s];
            for (int i = s; i < n + s; i++) {
                p[i] = in.nextInt();
            }
            return p;
        }

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

    static void exit(int a) {
        out.close();
        err.close();
        System.exit(a);
    }

    static InputStream inputStream = System.in;
    static OutputStream outputStream = System.out;
    static OutputStream errStream = System.err;
    static InputReader in = new InputReader(inputStream);
    static PrintWriter out = new PrintWriter(outputStream);
    static PrintWriter err = new PrintWriter(errStream);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

}