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

public class countingproblem {
	public static void main(String[] args) {
		FastScanner scan=new FastScanner();
		PrintWriter out=new PrintWriter(System.out);
		int t=scan.nextInt();
		for(int tt=0;tt<t;tt++) {
			int a=scan.nextInt(), b=scan.nextInt();
			int q=scan.nextInt();
			int lcm=a/gcd(a,b)*b;
			boolean[] same=new boolean[lcm];
			long delta=0;
			for(int i=0;i<lcm;i++) {
				same[i]=((i%a)%b==(i%b)%a);
				if(!same[i]) delta++;
			}
			int[] suffix=new int[lcm], prefix=new int[lcm];
			for(int i=0;i<lcm;i++) {
				if(!same[i]) prefix[i]++;
				if(i>0) prefix[i]+=prefix[i-1];
			}
			for(int i=lcm-1;i>=0;i--) {
				if(!same[i]) suffix[i]++;
				if(i+1<lcm) suffix[i]+=suffix[i+1];
			}
			
			for(int i=0;i<q;i++) {
				long res=0L;
				long l=scan.nextLong(), r=scan.nextLong();
				int lrem=(int)(l%lcm);
				int rrem=(int)(r%lcm);
				res+=suffix[lrem];
				res+=prefix[rrem];
				
				res+=((r-rrem)-(l-lrem+lcm))/lcm*delta;
				out.print(res);
				out.print(" ");
			}
			out.println();
		}
		out.close();
	}
	public static int gcd(int a, int b) {
		if(b==0) return a;
		return gcd(b,a%b);
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}

		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}

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

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

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

		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}
}
/*
1
199 200 5
1 1000000000000000000
2 41564543124
45645343 999999999999
1 2
2 3
*/