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

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cf1342c {
    static BufferedReader __in;
    static PrintWriter __out;
    static StringTokenizer input;

    public static void main(String[] args) throws IOException {
        __in = new BufferedReader(new InputStreamReader(System.in));
        __out = new PrintWriter(new OutputStreamWriter(System.out));
        
        int t = readInt();
        while(t --> 0) {
            read();
            int a = nextInt(), b = nextInt(), q = nextInt();
            /* if(a > b) {
                int swap = a;
                a = b;
                b = swap;
            }*/
            long[] cyc = new long[a * b + 1];
            for(int k = 1; k <= a * b; ++k) {
                cyc[k] = cyc[k - 1];
                if(((k - 1) % a) % b != ((k - 1) % b) % a) {
                    ++cyc[k];
                }
            }
            for(int i = 0; i < q; ++i) {
                read();
                long l = nextLong(), r = nextLong() + 1, lastM = r / (a * b) * (a * b), prevM = l / (a * b) * (a * b);
                // if(lastM <= r && lastM > l) {
                println(cyc[(int)(r - lastM)] + (lastM - prevM) / (a * b) * cyc[a * b] - cyc[(int)(l - prevM)]);
                // } else {
                //     assert lastM == prevM;
                // println(cyc[(int)(r - prevM)] - cyc[(int)(l - prevM)]);
                // }
            }
        }
        
        close();
    }

    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final long LMAX = 9223372036854775807L;
    static void read() throws IOException {input = new StringTokenizer(__in.readLine());}
    static String readLine() throws IOException {return __in.readLine();}
    static int nextInt() {return Integer.parseInt(input.nextToken());}
    static int readInt() throws IOException {return Integer.parseInt(__in.readLine());}
    static long nextLong() {return Long.parseLong(input.nextToken());}
    static void print(String s) {__out.print(s);}
    static void println(String s) {__out.println(s);}
    static void print(Object o) {__out.print(o);}
    static void println(Object o) {__out.println(o);}
    static void printy() {__out.println("Yes");}
    static void printY() {__out.println("YES");}
    static void printn() {__out.println("No");}
    static void printN() {__out.println("NO");}
    static void printyn(boolean b) {__out.println(b ? "Yes" : "No");}
    static void printYN(boolean b) {__out.println(b ? "YES" : "NO");}
    static void println(int... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), i++); __out.println(a[a.length - 1]);}
    static void println(long... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), i++); __out.println(a[a.length - 1]);}
    static void println() {__out.println();}
    static void close() {__out.close();}
}