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 int a,b,q,lcm,dp[];
		    static long f(long x) {
		    	return dp[lcm-1]*(x/lcm)+dp[(int)(x%lcm)];
		    }
		    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();
		    		lcm=(a*b)/(int)gcd(a,b);
		    		dp=new int[lcm];
		    		for(int i=1;i<lcm;i++) dp[i]=dp[i-1]+((i%a)%b!=(i%b)%a?1:0);
		    		while(q-->0) {
		    			long l=sc.nextLong(),r=sc.nextLong();
		    			out.print((f(r)-f(l-1))+" ");
		    		}
		    		out.println();
		    	}
		        out.flush();
		        out.close();
		    }
		}