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:
//package codeforces.contests.eduround86;

import java.io.*;
import java.util.*;

/**
 * @author tainic on Apr 26, 2020
 */
public class C {

    private static boolean LOCAL;
    static {
        try { LOCAL = "aurel".equalsIgnoreCase(System.getenv().get("USER")); } catch (Exception e){}
    }

    private static final String TEST = gen();

    private static String gen() {
        StringBuilder sb = new StringBuilder();
        sb.append(100).append("\n");
        for (int i = 0; i < 100; i++) {
            sb.append(143 + " " + 72 + " " + 500 + "\n");
            for (int j = 0; j < 500; j++) {
                sb.append(439 + " " + 2000000000 + "\n");
            }
        }
        return sb.toString();
    }
        /*"2\n" +
        "4 6 5\n" +
        "1 1\n" +
        "1 3\n" +
        "1 5\n" +
        "1 7\n" +
        "1 9\n" +
        "7 10 2\n" +
        "7 8\n" +
        "100 200";*/

    void solve(InputReader in, PrintWriter out) {
        int t = in.nextInt();
        while (t-- > 0) {
            long a = in.nextLong();
            long b = in.nextLong();
            int q = in.nextInt();

            long[] dxy = extendedGcd(a, b);
            long z = a / dxy[0] * b;

            Set<Long> x0s = new HashSet<>();
            for (int k1 = 0; k1 < a; k1++) {
                for (int k2 = 0; k2 < b; k2++) {
                    if (k1 % dxy[0] != k2 % dxy[0]) continue;

                    if (k1 % b != k2 % a) {
                        x0s.add(x0(k1, a, k2, b, dxy, z));
                    }
                }
            }


            Set<Long> y0s = new HashSet<>();
            boolean useY = false;
            if (x0s.size() > z / 2) {
                useY = true;
                for (int i = 0; i < z; i++) {
                    if (!x0s.contains((long)i)) y0s.add((long) i);
                }
            }

            /*System.out.println("z="+z);
            System.out.println(x0s.size());
            System.out.println(y0s.size());*/

            while (q-- > 0) {
                long L = in.nextLong();
                long R = in.nextLong();
                long ans = 0;

                if (!useY) {
                    for (long x0 : x0s) {
                        ans += ff(L, R, x0, z);
                    }
                } else {
                    ans = R- L +1;
                    for (long y0 : y0s) {
                        ans -= ff(L, R, y0, z);
                    }
                }
                out.print(ans + (q > 0 ? " " : ""));
            }
            out.println();
        }
    }

    private long ff(long L, long R, long x0, long z) {
        if (x0 > R) return 0;
        long c1 = (L <= x0) ? 0 : (L - x0) / z + ((L - x0) % z > 0 ? 1 : 0);
        long c2 = (R - x0) / z;
        return c2 - c1 + 1;
    }

    private long f(long L, long R, long a, long b) {
        long ans = 0;
        for (int k1 = 0; k1 < a; k1++) {
            for (int k2 = 0; k2 < b; k2++) {
                if (k1 % b != k2 % a) {
                    ans += g(L, R, k1, a, k2, b);
                    /*if (g(L, R, k1, a, k2, b) != g2(L, R, k1, a, k2, b)) {
                        System.out.println(L + " " + R + " " + k1 +" "+ a+" "+ k2+" "+ b);
                        g(L, R, k1, a, k2, b);
                        g2(L, R, k1, a, k2, b);
                    }*/
                }
            }
        }
        return ans;
    }

    private long g2(long L, long R, long k1, long a, long k2, long b) {
        long x = L;
        long ans = 0;
        while (x <= R) {
            if (x % a == k1 && x % b == k2) {
                ans++;
            }
            x++;
        }
        return ans;
    }

    private long g(long L, long R, long k1, long a, long k2, long b) {
        long[] dxy = extendedGcd(a, b);
        if (k1 % dxy[0] != k2 % dxy[0]) return 0;
        long z = a / dxy[0] * b;
        long x0 = ((k1 * dxy[2] * b + k2 * dxy[1] * a) / dxy[0]);
        if (x0 < 0) x0 += z * (-x0 / z + 1);
        x0 %= z;
        if (x0 > R) return 0;
        long c1 = (L <= x0) ? 0 : (L - x0) / z + ((L - x0) % z > 0 ? 1 : 0);
        long c2 = (R - x0) / z;
        return c2 - c1 + 1;
    }

    private long x0(long k1, long a, long k2, long b, long[] dxy, long z) {
        long x0 = ((k1 * dxy[2] * b + k2 * dxy[1] * a) / dxy[0]);
        if (x0 < 0) x0 += z * (-x0 / z + 1);
        x0 %= z;
        return x0;
    }

    /**
     * Returns [d, x, y], where
     *   d = gcd(a, b)
     *   a * x + b * y = d
     */
    public static long[] extendedGcd(long a, long b) {
        // d = gcd(a, b) = a * x + b * y
        //   = gcd(b, a % b) = b * x' + (a % b) * y' = b * x' + (a - b * (a / b)) * y' = a * y' + b(x' - (a / b) * y')
        // => x = y'
        //    y = x' - (a / b) * y'
        if (b == 0) {
            return new long[]{a, 1, 0};
        } else {
            long[] dxy = extendedGcd(b, a % b);
            return new long[]{dxy[0], dxy[2], dxy[1] - (a / b) * dxy[2]};
        }
    }

    //region util
    static class Util {

        private static final Random R = new Random();

        public static void sort(int[] a) {
            sort(a, 0, a.length - 1);
        }

        private static void sort(int[] a, int from, int to) {
            if (from >= to) {
                return;
            }

            // partition
            int pivotIndex = R.nextInt(to - from + 1) + from;
            int pivot = a[pivotIndex];
            // maintain this invariant, at each step i:
            // a[j] <  pivot, for j = fromIndex to lt - 1
            // a[j] == pivot, for j = lt to i - 1
            // a[j] >  pivot, for j = gt + 1 to toIndex
            int lt = from;
            int gt = to;
            int i = lt;
            while (i <= gt) {
                int cmp = a[i] - pivot;
                if (cmp < 0) {
                    swap(a, i, lt);
                    i++;
                    lt++;
                } else if (cmp > 0) {
                    swap(a, i, gt);
                    gt--;
                } else {
                    i++;
                }
            }

            // sort left and right
            sort(a, from, lt - 1);
            sort(a, gt + 1, to);
        }

        public static int findFirst(int[] a, int key) {
            return findFirstOrLast(a, key, 0, a.length - 1, -1);
        }

        public static int findLast(int[] a, int key) {
            return findFirstOrLast(a, key, 0, a.length - 1, 1);
        }

        static int findFirstOrLast(int[] a, int key, int fromIndex, int toIndex, int dir) {
            int left = fromIndex;
            int right = toIndex;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                int cmp = key - a[mid];
                if (cmp > 0) {
                    left = mid + 1;
                } else if (cmp < 0) {
                    right = mid - 1;
                } else if (dir == -1 && mid > fromIndex && a[mid - 1] == key) {
                    right = mid - 1;
                } else if (dir == 1 && mid < toIndex && a[mid + 1] == key) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -left - 1;
        }

        public static int findFirst(long[] a, long key) {
            return findFirstOrLast(a, key, 0, a.length - 1, -1);
        }

        public static int findLast(long[] a, long key) {
            return findFirstOrLast(a, key, 0, a.length - 1, 1);
        }

        static int findFirstOrLast(long[] a, long key, int fromIndex, int toIndex, int dir) {
            int left = fromIndex;
            int right = toIndex;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                int cmp = Long.compare(key,a[mid]);
                if (cmp > 0) {
                    left = mid + 1;
                } else if (cmp < 0) {
                    right = mid - 1;
                } else if (dir == -1 && mid > fromIndex && a[mid - 1] == key) {
                    right = mid - 1;
                } else if (dir == 1 && mid < toIndex && a[mid + 1] == key) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -left - 1;
        }

        public static <T extends Comparable<T>> int findFirst(List<T> a, T key) {
            return findFirstOrLast(a, key, 0, a.size() - 1, -1);
        }

        public static <T extends Comparable<T>> int findLast(List<T> a, T key) {
            return findFirstOrLast(a, key, 0, a.size() - 1, 1);
        }

        static <T extends Comparable<T>> int findFirstOrLast(List<T> a, T key, int fromIndex, int toIndex, int dir) {
            int left = fromIndex;
            int right = toIndex;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                int cmp = key.compareTo(a.get(mid));
                if (cmp > 0) {
                    left = mid + 1;
                } else if (cmp < 0) {
                    right = mid - 1;
                } else if (dir == -1 && mid > fromIndex && a.get(mid - 1) == key) {
                    right = mid - 1;
                } else if (dir == 1 && mid < toIndex && a.get(mid + 1) == key) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -left - 1;
        }

        public static void swap(int[] a, int i, int j) {
            if (i != j) {
                int ai = a[i];
                a[i] = a[j];
                a[j] = ai;
            }
        }

        public static int[] readInts(InputReader in, int k) {
            int[] a = new int[k];
            for (int i = 0; i < k; i++) {
                a[i] = in.nextInt();
            }
            return a;
        }

    }
    //endregion

    //region main
    public static void main(String[] args) throws Exception {
        long t = System.currentTimeMillis();

        try (
            InputReader in = new StreamInputReader(!LOCAL ? System.in : new ByteArrayInputStream(TEST.getBytes()));
            PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 2048), false)
        ) {
            new C().solve(in, out);
        }

        System.err.println("time: " + (System.currentTimeMillis() - t) + "ms");
    }
    //endregion

    //region fast io
    abstract static class InputReader implements AutoCloseable {

        public abstract int read();

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }

    static class StreamInputReader extends InputReader {

        private InputStream stream;
        private byte[] buf;
        private int curChar, numChars;

        public StreamInputReader(InputStream stream) {
            this(stream, 2048);
        }

        public StreamInputReader(InputStream stream, int bufSize) {
            this.stream = stream;
            this.buf = new byte[bufSize];
        }

        @Override
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        @Override
        public void close() throws Exception {
            stream.close();
        }

    }
    //endregion

    //region imports
    //endregion

}