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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CYetAnotherCountingProblem solver = new CYetAnotherCountingProblem();
        solver.solve(1, in, out);
        out.close();
    }

    static class CYetAnotherCountingProblem {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int t = in.scanInt();


            while (t-- > 0) {
                int a = in.scanInt();
                int b = in.scanInt();
                int q = in.scanInt();


                int lcm = (int) CodeX.LCM(a, b);


                int arr[] = new int[lcm];
                for (int i = 0; i < lcm; i++) arr[i] = (((i % a) % b) != ((i % b) % a)) ? 1 : 0;

                long pre[] = new long[lcm];
                pre[0] = arr[0];
                for (int i = 1; i < lcm; i++) pre[i] = pre[i - 1] + arr[i];


                while (q-- > 0) {
                    long l = in.scanLong();
                    long r = in.scanLong();
                    long ans = 0;

                    int right = (int) (r % lcm);
                    int left = (int) (l % lcm);

                    if (r - l + 1 <= lcm) {
                        if (left <= right) {
                            ans += pre[right] - ((left - 1) >= 0 ? pre[left - 1] : 0);
                        } else {
                            ans += pre[right];
                            ans += (pre[lcm - 1] - ((left - 1) >= 0 ? pre[left - 1] : 0));
                        }
                    } else {

                        ans += pre[right];
                        ans += (pre[lcm - 1] - ((left - 1) >= 0 ? pre[left - 1] : 0));

                        long nextL = (long) (l + (lcm - (l % lcm)));
                        long nextR = r - (r % lcm) - 1;
                        if (nextL <= nextR) {
                            long count = (nextR - nextL + 1) / lcm;
                            ans += (count * pre[lcm - 1]);
                        }


                    }

                    out.print(ans + " ");


                }
                out.println();

            }

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public long scanLong() {
            long I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

    }

    static class CodeX {
        public static long GCD(long A, long B) {
            if (B == 0)
                return A;
            else
                return GCD(B, A % B);
        }

        public static long LCM(long A, long B) {
            return ((A * B) / GCD(A, B));
        }

    }
}