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


public class C {

    static class SegmentTree {

        /**
         * Provides interface to perform operations on range queue like sum, min or max
         */

        interface Operation {
            int perform(int a, int b);
        }

        static class SumOperation implements Operation {
            @Override
            public int perform(int a, int b) {
                return a + b;
            }
        }


        public int[] createTree(int[] input, Operation operation) {
            int height = (int) Math.ceil(Math.log(input.length) / Math.log(2));
            int[] segmentTree = new int[(int) (Math.pow(2, height + 1) - 1)];
            createTreeUtil(segmentTree, input, 0, input.length - 1, 0, operation);
            return segmentTree;
        }

        private void createTreeUtil(int[] segmentTree, int[] input, int low, int high, int pos, Operation operation) {
            if (low == high) {
                segmentTree[pos] = input[low];
                return;
            }
            int mid = (low + high) / 2;
            createTreeUtil(segmentTree, input, low, mid, 2 * pos + 1, operation);
            createTreeUtil(segmentTree, input, mid + 1, high, 2 * pos + 2, operation);
            segmentTree[pos] = operation.perform(segmentTree[2 * pos + 1], segmentTree[2 * pos + 2]);
        }

        /**
         * RangeQuery segment tree for certain range (when not applied with lazy)
         */

        public int rangeQuery(int[] segmentTree, int qlow, int qhigh, int len, Operation operation) {
            return rangeQueryUtil(segmentTree, 0, len - 1, qlow - 1, qhigh - 1, 0, operation);
        }

        private int rangeQueryUtil(int[] segmentTree, int low, int high, int qlow, int qhigh, int pos, Operation operation) {
            if (qlow <= low && qhigh >= high) {
                return segmentTree[pos];
            }
            if (qlow > high || qhigh < low) {
                return 0;
            }
            int mid = (low + high) / 2;
            return operation.perform(rangeQueryUtil(segmentTree, low, mid, qlow, qhigh, 2 * pos + 1, operation),
                    rangeQueryUtil(segmentTree, mid + 1, high, qlow, qhigh, 2 * pos + 2, operation));
        }
    }
        public static void main(String[] args) throws IOException {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(inp.readLine());
        while (t-->0){
            String[] s1 = inp.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            int b = Integer.parseInt(s1[1]);
            int q = Integer.parseInt(s1[2]);

            long sum = 0;
            int[] check = new int[a*b+1];
            long[] at = new long[a*b+1];

            int size = a*b+1;
            for(int i=1;i<size;i++){
                if((i%a)%b!=(i%b)%a){
                    check[i]++;
                    sum++;
                }
                at[i] = sum;
            }

            size--;
            while (q-->0){


                long ans = 0;
                s1 = inp.readLine().split(" ");
                long l = Long.parseLong(s1[0]);
                long r = Long.parseLong(s1[1]);

                long rem = l%size;
                long rem2 = r%size;
                long x = 0;
                if(rem==0){
                    x = (l / size) * sum - check[size];
                }
                else {
                    x = (l / size) * sum + at[(int) rem - 1];
                }
                long y =  (r/size) *sum + at[(int)rem2];

                ans = y-x;
                out.write(ans+" ");



            }
            out.write("\n");




        }

        out.flush();


    }


    private static void merge(int[] arr, int left, int middle, int right) {

        int size1 = middle - left + 1;
        int size2 = right - middle;

        /* Create temp arrays */
        int[] Left = new int [size1];
        int[] Right = new int [size2];

        /*Copy data to temp arrays*/
        for (int i=0; i<size1; ++i) {
            Left[i] = arr[left + i];
        }
        for (int j=0; j<size1; ++j) {
            Right[j] = arr[middle + 1 + j];
        }

        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = left;
        while (i < size1 && j < size2)
        {
            if (Left[i] <= Right[j])
            {
                arr[k] = Left[i];
                i++;
            }
            else
            {
                arr[k] = Right[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < size1)
        {
            arr[k] = Left[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < size2)
        {
            arr[k] = Right[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
// merge()
    static void sort(int[] arr, int left, int right) {
        if (left < right)
        {
            // Find the middle point
            int m = (left+right)/2;

            // Sort first and second halves
            sort(arr, left, m);
            sort(arr , m+1, right);

            // Merge the sorted halves
            merge(arr, left, m, right);
        }
    }

    private static void merge(long[] arr, int left, int middle, int right) {

        int size1 = middle - left + 1;
        int size2 = right - middle;

        /* Create temp arrays */
        long[] Left = new long [size1];
        long[] Right = new long [size2];

        /*Copy data to temp arrays*/
        for (int i=0; i<size1; ++i) {
            Left[i] = arr[left + i];
        }
        for (int j=0; j<size1; ++j) {
            Right[j] = arr[middle + 1 + j];
        }

        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = left;
        while (i < size1 && j < size2)
        {
            if (Left[i] <= Right[j])
            {
                arr[k] = Left[i];
                i++;
            }
            else
            {
                arr[k] = Right[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < size1)
        {
            arr[k] = Left[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < size2)
        {
            arr[k] = Right[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
// merge()
    static void sort(long[] arr, int left, int right) {
        if (left < right)
        {
            // Find the middle point
            int m = (left+right)/2;

            // Sort first and second halves
            sort(arr, left, m);
            sort(arr , m+1, right);

            // Merge the sorted halves
            merge(arr, left, m, right);
        }
    }

    static long[] decToBinary(long n,long k)
    {
        // array to store binary number
        long[] binaryNum = new long[64];

        // counter for binary array
        int i = 0;
        while (n > 0L) {
            // storing remainder in binary array
            binaryNum[i] = n % k;
            n = n / k;
            i++;
        }
        return binaryNum;
    }
    static void print(int[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(int[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void print(boolean[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(boolean[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void print(long[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(long[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void print(String[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(String[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static long calc(int a,int b){
        long c = b-a+1;
        c = c*(c+1);
        c/=2l;
        return c;
    }
}