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:
	/*	/ ﾌﾌ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ム
		/ )\⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀  Y
		(⠀⠀| ( ͡° ͜ʖ ͡°）⠀⌒(⠀ ノ
		(⠀ ﾉ⌒ Y ⌒ヽ-く __／
		| _⠀｡ノ| ノ｡ |/
		(⠀ー '_人`ー ﾉ
		⠀|\ ￣ _人'彡ﾉ
		⠀ )\⠀⠀ ｡⠀⠀ /
		⠀⠀(\⠀ #⠀ /
		⠀/⠀⠀⠀/ὣ====================D-
		/⠀⠀⠀/⠀ \ \⠀⠀\
		( (⠀)⠀⠀⠀⠀ ) ).⠀)
		(⠀⠀)⠀⠀⠀⠀⠀( | /
		|⠀ /⠀⠀⠀⠀⠀⠀ | /
		[_] ⠀⠀⠀⠀⠀[___]                     */
	// Main Code at the Bottom
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	import java.math.BigInteger; 
	public class Main {
		//Fast IO class
	    static class FastReader {
	        BufferedReader br; 
	        StringTokenizer st; 
	        public FastReader() {
	        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
	        	if(!env) {
	        		try {
						br=new BufferedReader(new FileReader("src\\input.txt"));
					} catch (FileNotFoundException e) {
						e.printStackTrace();
					}
	        	}
	        	else 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; 
	        } 
	    }     
	    static long MOD=1000000000+7;
	    //Euclidean Algorithm
	    static long gcd(long A,long B){
	    	return (B==0)?A:gcd(B,A%B);
	    }
	    //Modular Exponentiation
	    static long fastExpo(long x,long n){
	        if(n==0) return 1;
	        if((n&1)==0) return fastExpo((x*x)%MOD,n/2)%MOD;
	        return ((x%MOD)*fastExpo((x*x)%MOD,(n-1)/2))%MOD;
	    }
	    //Modular Inverse
	    static long inverse(long x) {
	    	return fastExpo(x,MOD-2);
	    }
	    //Prime Number Algorithm
	    static boolean isPrime(long n){
	        if(n<=1) return false;
	        if(n<=3) return true;
	        if(n%2==0 || n%3==0) return false;
	        for(int i=5;i*i<=n;i+=6) if(n%i==0 || n%(i+2)==0) return false;
	        return true;
	    }
	    //Reverse an array
	    static void reverse(char arr[],int l,int r){
	    	while(l<r) {
	    		char tmp=arr[l];
	    		arr[l++]=arr[r];
	    		arr[r--]=tmp;
	    	}
	    }
	    //Print array
	    static void print1d(int arr[]) {
	    	out.println(Arrays.toString(arr));
	    }
	    static void print2d(int arr[][]) {
	    	for(int a[]: arr) out.println(Arrays.toString(a));
	    }
	    // Pair
	    static class pair{
	    	int x,y;
	    	pair(int a,int b){
	    		this.x=a;
	    		this.y=b;
	    	}
	    	public boolean equals(Object obj) {
	    		if(obj == null || obj.getClass()!= this.getClass()) return false;
	            pair p = (pair) obj;
	            return (this.x==p.x && this.y==p.y);
	        }
	    	public int hashCode() {
	            return Objects.hash(x,y);
	        }
	    }
	    static FastReader sc=new FastReader();
	    static PrintWriter out=new PrintWriter(System.out);  
	    //Main function(The main code starts from here
	    static long a,b,q,z;
	    static long solve(long x) {
	    	long ans=(x/z)*(z-a);
	    	x%=z;
	    	if(x>=a) ans+=(x-a+1);
	    	return ans;
	    }
	    public static void main (String[] args) throws java.lang.Exception {
	    	int test=1;
	    	test=sc.nextInt();
	    	while(test-->0){
	    		a=sc.nextInt();b=sc.nextInt();q=sc.nextInt();
	    		if(b>a) {
	    			long tmp=a;
	    			a=b;
	    			b=tmp;
	    		}
	    		z=(a*b)/gcd(a,b);
	    		while(q-->0) {
	    			long l=sc.nextLong(),r=sc.nextLong();
	    			out.print((solve(r)-solve(l-1))+" ");
	    		}
	    		out.println();
	    	}
	        out.flush();
	        out.close();
	    }
	}