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

public class TaskC {

    private static BufferedReader in;
    private static StringTokenizer tok;
    private static PrintWriter out;

    public static String readToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public static int readInt() throws IOException {
        return Integer.parseInt(readToken());
    }

    public static long readLong() throws IOException {
        return Long.parseLong(readToken());
    }

    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        run();
        in.close();
        out.close();
    }

    static int gcd(int a, int b){
        return b == 0 ? a : gcd(b,a % b);
    }

    static int lcm(int a, int b){
        return a / gcd(a, b) * b;
    }

    public static void run() throws IOException {
        // logic here
        int t = readInt();
        for (int i = 0; i < t; i++) {
            int a = readInt();
            int b = readInt();
            int c = lcm(a, b);
            int[] d = new int[c + 1];
            int cnt = 0;
            for (int x = 1; x <= c; x++) {
                if (((x % a) % b) != ((x % b) % a)) {
                    cnt++;
                }
                d[x] = cnt;
            }
            int q = readInt();
            for (int j = 0; j < q; j++) {
                long l = readLong();
                long r = readLong();
                long res = 0;
                long l1 = l;
                if (l % c != 1) {
                    l1 = (l / c + 1) * c + 1;
                    if (l % c == 0) {
                        res += d[c] - d[c - 1];
                    } else {
                        res += d[c] - d[(int)(l % c) - 1];
                    }
                }

                long r1 = r + 1;
                if (r % c != 0) {
                    r1 = (r / c) * c + 1;
                    if (r % c == 1) {
                        res += d[1];
                    } else {
                        res += d[(int) (r % c)] - d[1];
                    }
                }

                res += ((r1 - l1) / c) * cnt;

                System.out.print(res + " ");
            }
            System.out.println();
        }
    }
}