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.IOException;
import java.util.Scanner;

public class Main {

	public static long gcd(long a, long b) {
		if(a>b) {
			if(a%b==0) {
				return b;
			}
			else {
				return gcd(a,a%b);
			}
		}
		else {
			return gcd(b,a);
		}
	}
	
	public static long lcm(long a, long b) {
		return a*b/gcd(a,b);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for (int test_case = 1; test_case <= T; test_case++) {
			
			long a = sc.nextLong();
			long b = sc.nextLong();
			long lcm = lcm(a,b);
			long bigger = a>b?a:b;
			
			int q = sc.nextInt();
			
			for (int i = 0; i < q; i++) {
				long cnt=0;
				long l = sc.nextLong();
				long r = sc.nextLong();
				
				long left = l/lcm;	//내림
				long right = r/lcm;
				
				
				if(left==right) {
					cnt=0;
//					[l~r]
//					[lcm*left vs l ~ lcm*left+bigger vs r]
					long temp = Math.min(lcm*left+bigger-1, r) - Math.max(lcm*left, l) + 1;
//					System.out.println("temp:"+temp);
					cnt = temp>0?temp:0; 
				}
				else {
					cnt = (right-left-1)*bigger;
//					System.out.println("init cnt:"+cnt);
//				왼쪽 경계검사
					long temp = Math.min(lcm*left+bigger-1, r) - Math.max(lcm*left, l) + 1;
//					System.out.println("left temp:"+temp);
					cnt -= temp>0?temp:0; 
//				오른쪽 경계검사
					temp = Math.min(lcm*right+bigger-1, r) - Math.max(lcm*right, l) + 1;
//					System.out.println("right temp:"+temp);
					cnt += temp>0?temp:0; 
				}
//				System.out.println("cnt:"+cnt);
				System.out.print((r-l+1)-cnt+" ");
			}
			System.out.println();
			
//			for (int j = 0; j < 100; j++) {
//				System.out.print(j+"\t"+(j%a)%b+" "+(j%b)%a+"\t");
//				if((j%a)%b!=(j%b)%a) {
//					System.out.print("XXX");
//				}
//				System.out.println();
//			}
		}
	}
}
/*
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 3
7 8
100 200
100 145
*/