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

public class CountingModMod {
    public static void main(String[] args) {
        try (FastReader reader = new FastReader();
             PrintWriter writer = new PrintWriter(System.out)) {
            int tc = reader.nextInt();
            while (tc-- > 0) {
                long a = reader.nextInt();
                long b = reader.nextInt();
                long min = Math.min(a, b);
                long max = Math.max(a, b);
                long x = a * b / gcd(min, max);
                int q = reader.nextInt();
                while (q-- > 0) {
                    long l = Long.parseLong(reader.nextToken()) - 1;
                    long r = Long.parseLong(reader.nextToken());
                    long count = l/x * max + Math.min(l - l/x * x + 1, b);
                    // to avoid overflow
                    count *= -1;
                    count += r/x * max + Math.min(r - r/x * x + 1, b);
                    count = r - l - count;
                    writer.write(count + " ");
                }
                writer.write("\n");
            }
        }
    }

    private static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    static class FastReader implements AutoCloseable {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public FastReader() {
            this(System.in);
        }

        public FastReader(InputStream inputStream) {
            this.reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        private String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                String line = nextLine();
                Objects.requireNonNull(line);
                tokenizer = new StringTokenizer(line);
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            String next = nextToken();
            Objects.requireNonNull(next);
            return Long.parseLong(next);
        }

        public int nextInt() {
            String next = nextToken();
            Objects.requireNonNull(next);
            return Integer.parseInt(next);
        }

        @Override
        public void close() {
            try {
                reader.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }
    }
}
