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

public class Main {
	
	private static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
	
	private static int gcd(int i, int j) {
		return (j == 0) ? i : gcd(j, i % j);
	}
	
	private static void solveTC(int __) {
		
		/* For Google */
//		ans.append("Case #").append(__).append(": ");
		
		//code start
		
		long a = scn.nextInt(), b = scn.nextInt(), q = scn.nextInt();
		if (a < b) {
			a = a + b;
			b = a - b;
			a = a - b;
		}
		
		long perod = lcm((int) a, (int) b) / a;
		
		while (q-- > 0) {
			long l = scn.nextLong(), r = scn.nextLong();
			if (r - l >= 1000) {
				long lb = (l / a + 1), rb = (r / a);
				long minus = rb / perod - lb / perod;
				minus *= a;
				
				long count = 0;
				for (long i = l; i < lb * a; i++) {
					if (((i % a) % b) == ((i % b) % a)) {
						count++;
					}
				}
				for (long i = rb * a + 1; i <= r; i++) {
					if (((i % a) % b) == ((i % b) % a)) {
						count++;
					}
				}
				minus += count;
				print(r - l + 1 - minus);
			} else {
				int count = 0;
				for (long i = l; i <= r; i++) {
					if (((i % a) % b) == ((i % b) % a)) {
						count++;
					}
				}
				print(r - l + 1 - count);
			}
			print(" ");
		}
		
		//code end
		
		ans.append("\n");
	}
	
	static void print(Object obj) {
		ans.append(obj.toString());
	}
	
	public static void main(String[] args) {
		
		scn = new Scanner();
		int t = scn.nextInt();
//		int t = 1;
		for (int i = 1; i <= t; i++) {
			ans = new StringBuilder();
			solveTC(i);
			System.out.print(ans);
		}
		
	}
	
	static Scanner scn;
	static StringBuilder ans;
	
	//Fast Scanner
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;
		
		public Scanner() {
			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;
		}
		
		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextInt();
			}
			return array;
		}
		
		Integer[] nextIntegerArray(int n) {
			Integer[] array = new Integer[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextInt();
			}
			return array;
		}
		
		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextLong();
			}
			return array;
		}
		
		String[] nextStringArray() {
			return nextLine().split(" ");
		}
		
		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++) {
				array[i] = next();
			}
			return array;
		}
	}
}