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.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.Vector;

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.pow;
import static java.lang.Math.abs;
import static java.util.Arrays.sort;
import static java.util.Arrays.parallelSort;
import static java.util.Arrays.binarySearch;

public class cf {
    static final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    static final int mod = (int) (1e9 + 7);
    static final int modf = 998244353;
    static final Reader r = new Reader();
    static final PrintWriter out = new PrintWriter((new BufferedOutputStream(System.out)));
    int[] level, p;
    Vector<Integer>[] adj;

    public static void main(final String[] args) throws Exception {
        final int testcases = hasTestCases ? r.nextInt() : 1;
        for (int i = 0; i < testcases; i++) {
            final long an = new cf().solve();
            if (hasPrint)
                if (hasBooleanPrint)
                    out.println(an == 0 ? "no" : "yes");
                else
                    out.println(an);
            // out.print("Case "+i+1+": ");
        }
        out.flush();
    }

    static final boolean hasTestCases = true, fastIO = true;
    static final boolean hasPrint = false, hasBooleanPrint = false;
    static final int lineLength = 1000002;

    private long solve() throws Exception {
        int a = ni(), b = ni(), q = ni();
        for (int i = 0; i < q; i++) {
            long l = nl(), r = nl(),ll=l;
            long c = 0, lcm = (a * b) / gcd(a, b);
            for (long j = l; j < lcm + 1 && j < r + 1; j++) {
                if ((j % a) % b == (j % b) % a) {
                    c++;
                }
                ll=j;
            }

            long dr = r / lcm, dl = (long) Math.ceil(l / (double) lcm);
            //if(l/lcm==0)dl--;
            for (long j = ll;j>lcm && j < dl*lcm; j++) {
                if ((j % a) % b == (j % b) % a) {
                    c++;
                }
            }
            dr-=dl-1;
            c+=dr*max(a, b);
            p(((r - l + 1) - c) + " ");
        }
        pn("");
        return 1;
    }

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

    static String n() throws Exception {
        return fastIO ? r.next() : in.next();
    }

    static String nln() throws Exception {
        return fastIO ? r.nextLine() : in.nextLine();
    }

    static int ni() throws Exception {
        return fastIO ? r.nextInt() : in.nextInt();
    }

    static long nl() throws Exception {
        return fastIO ? r.nextLong() : in.nextLong();
    }

    static double nd() throws Exception {
        return fastIO ? r.nextDouble() : in.nextDouble();
    }

    static void p(final Object o) {
        out.print(o);
    }

    static void pn(final Object o) {
        out.println(o);
    }

    static void pni(final Object o) {
        out.println(o);
        out.flush();
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 19;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        private StringTokenizer st;
        private final BufferedReader br;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public Reader(final String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            br = new BufferedReader(new FileReader(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String next() throws Exception {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (final IOException e) {
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        public String nextLine() throws Exception {
            String str = "";
            try {
                str = br.readLine();
            } catch (final IOException e) {
                throw new Exception(e.toString());
            }
            return str;
        }

        public String readLine() throws IOException {
            final byte[] buf = new byte[lineLength]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

}