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.util.*;
import java.io.*;
 
public class C {
    public static long lcm;
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner(System.in);
        PrintWriter output = new PrintWriter(System.out);

        int T = input.nextInt();
        for (int t = 0; t < T; t++) {
            long a = input.nextLong(), b = input.nextLong(), q = input.nextInt();
            if (a < b) {
                long temp = a;
                a = b;
                b = temp;
            }
            lcm = lcm(a, b);

            for (int i = 0; i < q; i++) {
                long l = input.nextLong(), r = input.nextLong();
                if (i == 0)
                    System.out.print(getCount(a, b, l, r));
                else
                    System.out.print(" " + getCount(a, b, l, r));
            }
            System.out.println();
        }

        output.close();
    }
 
    public static long getCount(long a, long b, long l, long r) {
        if (a == b)
            return 0;


        long start = l / lcm * lcm;
        long finish = r / lcm * lcm;
        long count = (finish - start) / lcm * a;
        if (start + a <= l)
            count -= a;
        else 
            count -= (l - start);

        if (r - finish >= a)
            count += a;
        else 
            count += (r - finish + 1);

        return r - l + 1 - count;
    }

    public static long gcd(long x, long y) {
        if (x == 0 || y == 0)
            return x + y;
        
        if (x > y)
            return gcd(x % y, y);

        return gcd(x, y % x);
    }

    public static long lcm(long x, long y) {
        return x * y / gcd(x, y);
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }
 
        FastScanner(FileReader s) {
            br = new BufferedReader(s);
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            return br.readLine();
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }
}