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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

//import Number_theory.pair;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import graph_representation.edge;
public class hacker49 {
	public static int r1=0;
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            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 ArrayList<Integer>[] f=new ArrayList[1001];
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
int t=s.nextInt();
while(t>0) {
	long a=s.nextLong();
	long b=s.nextLong();
	long q=s.nextLong();
	long gcd=GCD(a,b);
	long lcm=(a*b)/gcd;
	while(q>0) {
		long l=s.nextLong();
		long r=s.nextLong();
		long ans=0;
		if(a==b) {
			out.print(0+" ");
		}else {
			long max=Math.max(a, b);
			
			if(l%lcm!=0) {
				long h=(l/lcm)+1;
				h*=lcm;
				if(h<=r) {
				ans+=(Math.max(0,h-Math.max(l,h-(lcm-max))));
//				System.out.println(ans);
				if(h!=r) {
					long f=r/lcm;
					h/=lcm;
					f-=h;
					ans+=f*(lcm-max);
//					System.out.println(ans);
					if(r%lcm!=0) {
						long p=r/lcm+1;
						long z=p*lcm;
						ans+=(Math.max(0, r-(z-(lcm-max))+1));
					}
				}
//				System.out.println(ans);
			}else {
				ans+=Math.max(0, (r-Math.max(l, h-(lcm-max))+1));
			}
			
			}else {
				long f=r/lcm;
				l/=lcm;
				f-=l;
				ans+=f*(lcm-max);
				if(r%lcm!=0) {
					long p=r/lcm+1;
					long z=p*lcm;
					ans+=(Math.max(0, r-(z-(lcm-max))+1));
				}
				
			}
			
		out.print(ans+" ");
		}
	
		q--;
	}
out.println();		
	t--;
}
out.close();
	}
	public static int lower_bound(ArrayList<Long> a ,int n,long x) {
		int l=0;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a.get(mid)<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}

	public static int[] is_prime=new int[1000001];
	public static ArrayList<Long> primes=new ArrayList<>();
 	public static void sieve() {
		long maxN=1000000;
		for(long i=1;i<=maxN;i++) {
			is_prime[(int) i]=1;
		}
		is_prime[0]=0;
		is_prime[1]=0;
		for(long i=2;i*i<=maxN;i++) {
			if(is_prime[(int) i]==1) {
//				primes.add((int) i);
				for(long j=i*i;j<=maxN;j+=i) {
					is_prime[(int) j]=0;
				}
			}
		}
		for(long i=0;i<=maxN;i++) {
			if(is_prime[(int) i]==1) {
				primes.add(i);
			}
		}
//		
	}
	static class pair implements Comparable<pair>{
		private long a;
		pair(long a){
			this.a=a;
		}
		public int compareTo(pair o) {
			return Long.compare(this.a, o.a);
		}
	}
	
	
	
	
	static int[] vis=new int[1001];
	static int[] deg=new int[1001];
	static int[] sub=new int[1001];
	static int dfs(int node) {
		vis[node]=1;	
		for(int i=0;i<f[node].size();i++) {
			if(vis[f[node].get(i)]==0) {
				sub[node]+=dfs(f[node].get(i));
			
			}
		}
		return (sub[node]+1);
		
	}
//	static class pair implements Comparable<pair>{
//		private int l;
//		private int r;
//		private long c;
//		pair(int l,int r,long c){
//			this.l=l;
//			this.r=r;
//			this.c=c;
//		}
//		public int compareTo(pair o) {
//			return Long.compare(this.c, o.c);
//		}
//	}
	
	
			public static long[] merge_sort(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort(A, start, mid);
			long[] o = merge_sort(A, mid + 1, end);
			return (merge(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] < b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	
	public static long im(long a) {
		return binary_exponentiation_1(a,mod-2)%mod;
	}
	public static long binary_exponentiation_1(long a,long n) {
		long res=1;
		while(n>0) {
			if(n%2!=0) {
				res=((res)%(1000000007) * (a)%(1000000007))%(1000000007);
				n--;
			}else {
				a=((a)%(1000000007) *(a)%(1000000007))%(1000000007);
				n/=2;
			}
		}
		return (res)%(1000000007);
		
	}

	public static long[] fac=new long[100001];
	public static void find_factorial() {
		fac[0]=1;
		fac[1]=1;
		for(int i=2;i<=100000;i++) {
			fac[i]=(fac[i-1]*i)%(mod);
		}
	}

	
	static long mod=1000000007;
	public static long GCD(long a,long b) {
		if(b==(long)0) {
			return a;
		}
		return GCD(b , a%b);
	}
	static long c=0;
	
		
	
}