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.*;
import java.util.*;
import java.math.*;

public class C {
    static final boolean RUN_TIMING = false;
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1024);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1024);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        int zzz = ipar();
        for (int zz = 0; zz < zzz; zz++) {
            int a = ipar();
            int b = ipar();
            int q = ipar();
            int ab = a*b;
            int[] prefix = new int[ab+1];
            for (int i = 1; i <= ab; i++) {
                prefix[i] = prefix[i-1];
                if ((i-1) % a % b != (i-1) % b % a) {
                    prefix[i]++;
                }
            }
            // out.println(Arrays.toString(prefix));
            for (int i = 0; i < q; i++) {
                long l = lpar()-1;
                long r = lpar();
                long lWhole = l / ab;
                int lRem = (int)(l % ab);
                long rWhole = r / ab;
                int rRem = (int)(r % ab);
                out.print(rWhole * prefix[ab] + prefix[rRem+1] - (lWhole * prefix[ab] + prefix[lRem+1]));
                out.print(" ");
            }
            out.println();
        }
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        StringBuilder sb = new StringBuilder(1024);
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            sb.append((char)c);
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return sb.toString();
    }

    public String linepar() throws IOException {
        StringBuilder sb = new StringBuilder(1024);
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            sb.append((char)c);
        }
        return sb.toString();
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new C().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time/1000000.0);
        }
        out.flush();
        in.close();
    }
}