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.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Main().new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Main solver = new Main();
		solver.solve(1, in, out);
		out.close();
	}
	
	// prefix sum
	public void solve(int testNumber, Scanner in, PrintWriter out) {
		int t = in.ni();
		for(int ia = 0; ia < t; ia++) {
			int a = in.ni();
			int b = in.ni();
			int lcm = lcm(a, b);
			int q = in.ni();
			for(int i = 0; i < q; i++) {
				long l = in.nl();
				long r = in.nl();
				long res = 0;
				
				// cases:
				// 1. both are in the same group --> find counts, subtract
				// 2. in groups next to each other --> find number of 0's in between
				// 3. multiple groups in between --> find number of groups in between, add front end
				
				if(l / lcm == r / lcm) {
					long countLeft = Math.max(0, l % lcm - b + 1);
					long countRight = Math.max(0, r % lcm - b + 1);
					
					if(countLeft == 0) res = countRight - countLeft;
					else res = countRight - countLeft + 1;
				} else {
					long countLeft = Math.min(lcm - b, lcm - l % lcm);
					long countRight = Math.max(0, r % lcm - b + 1);
					long countBet = (r / lcm - l / lcm - 1) * (lcm - b);
					res = countBet + countLeft + countRight;
				}
				
				// long divBoth = r / (a * b) - l / (a * b);
				
				// 01230123||0123 012301230123 01||25
				// 01230101||2301 012301012301 01||
				// 11111100||0000 111111000000 11||
				
				// 010101 010101
				// 010010 010010
				// 111000 111000
				
				// 01234560123456012345601234560123456012345601234560123456012345601234560
				// 01234560120123456012012345601201234560120123456012012345601201234560120
				// 11111111110000000000000000000000000000000000000000000000000000000000000
				/*long count = 0;
				for(long j = l; j <= r; j++) {
					long m1 = (j % a) % b;
					long m2 = (j % b) % a;
					if(m1 != m2) count++;
				}*/
				System.out.print(res + " ");// + count + " ");
			}
			System.out.println();
		}
	}
	static int gcd(int a, int b) 
    { 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
    } 
      
    // method to return LCM of two numbers 
    static int lcm(int a, int b) 
    { 
        return (a*b)/gcd(a, b); 
    }
	
	class Scanner {
		
		BufferedReader br;
		StringTokenizer in;
 
		public Scanner(InputStream inputStream) {
			br = new BufferedReader(new InputStreamReader(inputStream));
		}
 
		public String next() {
			return hasMoreTokens() ? in.nextToken() : null;
		}
 
		public String readLine() {
			try {
				return br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
				return null;
			}
		}
 
		boolean hasMoreTokens() {
			while (in == null || !in.hasMoreTokens()) {
				String s = readLine();
				if (s == null)
					return false;
				in = new StringTokenizer(s);
			}
			return true;
		}
 
		public String ns() {
			return next();
		}
 
		public int ni() {
			return Integer.parseInt(ns());
		}
		
		public long nl() {
			return Long.parseLong(ns());
		}
 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = ni();
			}
			return a;
		}
		
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nl();
			}
			return a;
		}
	}
}