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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class c {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		FastScanner sc = new FastScanner(in);
		PrintWriter out = new PrintWriter(System.out);

		int t = sc.nextInt();
		while (t-- > 0) {
			long a = sc.nextLong();
			long b = sc.nextLong();
			long min = Math.min(a ,b);
			long max = Math.max(a, b);
			long q = sc.nextLong();
			while(q-->0) {
				long l = sc.nextLong();
				long r = sc.nextLong();
				if(min == max ||r <= max ) {
					out.print(0+" ");
					continue;
				}
				
				long sub = 0 ;
				long total = r - l+1;
				
		        if(l<= max) {
		        	sub = sub + (max - l );
		        	l = max;
		        }
		        if(max <= r) {
		        long lcm = lcm(min , max);
		        long least_coef  = (l )  / lcm ;
		        long max_coef  = (r )  / lcm ;
		        
		        sub += (max_coef - least_coef+1) * max;
		        for(long i = least_coef*lcm ; i <least_coef*lcm + max ; i++ ) {
		        	if(i <l)
		        		sub--;
		        }
		        for(long i = max_coef*lcm ; i <max_coef*lcm + max ; i++ ) {
		        	if(i > r)
		        		sub--;
		        }
		        }
		        out.print((total - sub)+" ");    
			}
			out.println();
		}
		out.flush();
	}
	static long gcd(long a, long b) 
    { 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
    } 
      
    // method to return LCM of two numbers 
    static long lcm(long a, long b) 
    { 
        return (a*b)/gcd(a, b); 
    } 
	static class FastScanner {
		BufferedReader in;
		StringTokenizer st;

		public FastScanner(BufferedReader in) {
			this.in = in;
		}

		public String nextToken() throws Exception {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(in.readLine());
			}
			return st.nextToken();
		}

		public int nextInt() throws Exception {
			return Integer.parseInt(nextToken());
		}

		public long nextLong() throws Exception {
			return Long.parseLong(nextToken());
		}

		public double nextDouble() throws Exception {
			return Double.parseDouble(nextToken());
		}
	}
}
