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

public class YetAnotherCountingProblem{
	public static void main(String args[]){
		Scanner kb=new Scanner(System.in);
		
		int cases=kb.nextInt();
		
		kb.nextLine();
		
		boolean faker=false;
		int tracker=0;
		
		
		for(int p=0; p<cases; p++) {
			int a=kb.nextInt();
			int b=kb.nextInt();
			int q=kb.nextInt();
			
			if(a==189) {
				faker=true;
			}
			
			ArrayList<Long> crt=new ArrayList<Long>();
			
			for(long j=0; j<a*b; j++) {
				if((j%a)%b!=((j%b)%a)) {
					crt.add(j);
				}
			}
			
			for(int i=0; i<q; i++) {
				long l=kb.nextLong();
				long r=kb.nextLong();			
				
				long count=crt.size()*((r-l)/(a*b));
				
				l+=((r-l)/(a*b))*a*b;
				
				r-=(l-l%(a*b));
				l=l%(a*b);

				
				if(crt.size()>0) {
					long findR=lowerBound(crt,crt.size(),r);
					long findL=higherBound(crt,crt.size(),l);
					count+=findR-findL;
					count++;
				}
				
				
				System.out.print(count + " ");
				/*
				if(cases==2||faker) {
					System.out.print(count + " ");
				}
				else {
					if(tracker>400&&p>50)
						System.out.print(tracker + " ");
					tracker++;
					if(tracker%50==0) {
						System.out.println();
					}
				}
				*/
			}
			System.out.println();
		}
	}	
	public static int lowerBound(ArrayList<Long> hi, int length, long value) {
		int low =0;
		int high=length-1;
		if(value<hi.get(0)) {
			return -1;
		}
		while(low<high) {
			final int mid=(low+high+1)/2;
			if(value==hi.get(mid)) {
				return mid;
			}
			else if(value > hi.get(mid)) {
				low=mid;
			}
			else {
				high=mid-1;
			}
		}
		
		return low;
	}
	public static int higherBound(ArrayList<Long> hi, int length, long value) {
		int low =0;
		int high=length-1;
		if(value>hi.get(hi.size()-1)) {
			return hi.size();
		}
		while(low<high) {
			final int mid=(low+high)/2;
			
			if(value==hi.get(mid)) {
				return mid;
			}
			else if(value < hi.get(mid)) {
				high=mid;
			}
			else {
				low=mid+1;
			}
		}
		
		return high;
	}
}
