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.math.*;
import java.util.*;
public class Main
{
	static class FastReader
    {
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public FastReader() { this(System.in); }public FastReader(InputStream is) { mIs = is;}
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];}
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;}
        public String next(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();}
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;}
        public int i(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;}
        public double d() throws IOException {return Double.parseDouble(next()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; }
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; }
        public void scanIntArr(int [] arr){ for(int li=0;li<arr.length;++li){ arr[li]=i();}}
        public void scanIntIndexArr(int [] arr){ for(int li=0;li<arr.length;++li){ arr[li]=i()-1;}}
        public void scanLongArr(long [] arr){for (int i=0;i<arr.length;++i){arr[i]=l();}}
        public void shuffle(int [] arr){ for(int i=arr.length;i>0;--i) { int r=(int)(Math.random()*i); int temp=arr[i-1]; arr[i-1]=arr[r]; arr[r]=temp; } }
        public int swapIntegers(int a,int b){return a;} //Call it like this: a=swapIntegers(b,b=a)
    }
	public static void main(String args[]) throws IOException{
		FastReader in = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int t =in.i();
		while(t-->0){
			int a=in.i(), b=in.i(), q=in.i();
			int lcm = (a*b)/gcd(a,b), max = Math.max(a,b);
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<q; i++){
				int l=in.i(), r = in.i(), count=0;
				boolean lt=p(l,max,lcm), rt=p(r,max,lcm);
				// out.println(lt+" "+rt);
				if(lt){
					do{
						l++;
						count++;
						// out.println(l+" "+);
					}while(p(l,max,lcm) && l<r);
				}
				if(rt){
					do{
						r--;
						count++;
					}while(p(r,max,lcm) && l<r);
				}
				if(r-l<max){
					sb.append(count+" ");
				}else{
					if((r-l)%lcm==0){
						count+=((r-l)/lcm)*(lcm-max);
					}else{
						count+=((r-l)/lcm+1)*(lcm-max);
					}
					sb.append(count+" ");
				}
			}
			out.println(sb);
		}
		out.flush();
        out.close();
	}
	static boolean p(int t, int max, int lcm){
	    if(lcm==max) return false;
	    int f = t/lcm;
	    return t>= lcm*f+max;
	}
	static int gcd(int a, int b){
	    if(a==0)
	    return b;
	    return gcd(b%a, a);
	}
}

