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.util.*;
import java.io.*;

public class C1342 {
	
	public static int gcd(int n, int m) {
		return n == 0 ? m : gcd(m % n, n);
	}
	
	public static int lcm(int n, int m) {
		return n * (m / gcd(n, m));
	}
	
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int t = sc.nextInt();
		while(t-->0) {
			int u = sc.nextInt(), v = sc.nextInt();
			int a = Math.min(u, v), b = Math.max(u, v);
			int g = lcm(a, b);
			int[] pre = new int[g];
			for(int i = 0; i < g; i++) {
				if((i % a) % b != (i % b) % a)
					pre[i] = (i == 0 ? 0 : pre[i - 1]) + 1;
				else
					pre[i] = (i == 0 ? 0 : pre[i - 1]);
			}
			
			int diff = pre[g - 1];
			int q = sc.nextInt();
			while(q-->0) {
				long l = sc.nextLong(), r = sc.nextLong();
				long cnt = 0;
				if(r - l + 1 < g) {
					//System.out.println("hi");
					int i = (int)(l % g);
					int j = (int)(r % g);
					if(i == 0)
						cnt = pre[j];
					else if(j >= i) {
						if(j == 0)
							j = diff;
						else
							j = pre[j];
						cnt = j - (i == 0 ? 0 : pre[i - 1]);
					} else {
						cnt = pre[j];
						cnt += pre[g - 1] - pre[i - 1];
					}
					pw.print(cnt + " ");
					continue;
				}
				
				cnt += (l % g == 0 ? 0 : pre[g - 1] - pre[(int)(l % g) - 1]);
				//System.out.println(cnt);
				cnt += pre[(int)(r % g)];
				//System.out.println(cnt);
				l = 1l * ((l + (g - 1)) / g) * g + 1;
				r = 1l * (r / g) * g;
				cnt += 1l * Math.max(0, (r - l + 1)) / g * diff;
				
				//System.out.println(l + " " + r);
				pw.print(cnt + " ");
			}
			pw.print("\n");
		}	
		
		
		pw.flush();
	}

	public static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();
			return array;
		}

		public Integer[] nextIntegerArray(int n) throws IOException {
			Integer[] array = new Integer[n];
			for (int i = 0; i < n; i++)
				array[i] = new Integer(nextInt());
			return array;
		}

		public long[] nextLongArray(int n) throws IOException {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();
			return array;
		}

		public double[] nextDoubleArray(int n) throws IOException {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();
			return array;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}