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.*;

public class Solution{

    int[] arr;
	public void build(int a, int b, int lcm) {
        arr = new int[lcm+1];

        for(int i=1;i<=lcm;i++){
            if((i%a)%b != (i%b)%a){
                arr[i] = arr[i-1]+1;
            }else{
                arr[i] = arr[i-1];
            }
        }
	}

    public int hcf(int a, int b){
        if(a==0) return b;

        return hcf(b%a, a);
    }

    public int lcm(int a, int b){
        return a*b/hcf(a, b);
    }

    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner(System.in);
        PrintWriter printWriter = new PrintWriter(System.out);
        int t = (int) scanner.nextInt();
        Solution sol = new Solution();

        for(int i=0;i<t;i++){
            int a = (int) scanner.nextInt();
            int b = (int) scanner.nextInt();
            int q = (int) scanner.nextInt();

            int lc = sol.lcm(a, b);
            sol.build(a, b, lc);
            
            int[] ret = new int[q];
            for(int j=0;j<q;j++){
                int l = (int) scanner.nextInt();
                int r = (int) scanner.nextInt();

                int ans1 = sol.arr[(l-1)%lc];
                int ans2 = sol.arr[r%lc];

                ret[j] = ans2-ans1 + sol.arr[lc]*((r-l+1)/lc);
            }

            for(int j=0;j<q;j++){
                printWriter.printf("%d ", ret[j]);
            }
            printWriter.print("\n");
        }

        printWriter.close();
    }
 
    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
 
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }
 
        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
 
            return tokenizer.nextToken("\n");
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
         
        public long nextInt() {
            return Integer.parseInt(next());
        }
 
    }
}