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

public class Main {

    public static void main(String[] args) {
	// write your code here
        FastReader scan = new FastReader();
        int test = scan.nextInt();
        for(int i=0;i<test;i++){
            int a = scan.nextInt();
            int b= scan.nextInt();
            int q = scan.nextInt();
            long[][] arr = new long[q][2];
            for(int j=0;j<q;j++){
                arr[j][0] = scan.nextLong();
                arr[j][1] = scan.nextLong();
            }

            boolean[] matching = new boolean[a*b+1];
            int[] arrsum = new int[a*b+1];
            for(int j=1;j<=a*b;j++){
                if( (j%a)%b == (j%b)%a){
                    matching[j] = true;
                    arrsum[j]=arrsum[j-1];
                }
                else{
                    arrsum[j]  = arrsum[j-1]+1;
                }
            }



            for(int j=0;j<q;j++){
                long l = arr[j][0];
                long r = arr[j][1];
                long mul = (r-l+1)/(a*b);
                long final_index = l+mul*(a*b);
                long ans = 0;
                for(long jj = final_index;jj<=r;jj++){
                    ans += (matching[(int)jj%(a*b)])?0:1;
                }
                ans+= mul * (arrsum[a*b]);
                System.out.println(ans);

            }
        }


    }

    public static long min(long a,long b){
        return a>b?b:a;
    }


    public static long max(long a,long b){
        return a>b?a:b;
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

}
