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 ProblemC
{
	public static BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer tokens;
	
	public static void main(String[] args) throws IOException
	{
		int numTestCases = Integer.parseInt(infile.readLine());
		for(int t = 1; t <= numTestCases; t++)
		{
			String[] temp = infile.readLine().split(" ");
			int a = Integer.parseInt(temp[0]);
			int b = Integer.parseInt(temp[1]);
			int q = Integer.parseInt(temp[2]);
			long lcm = findLCM(Math.min(a, b), Math.max(a, b));
			for(int i = 0; i < q; i++)
			{
				temp = infile.readLine().split(" ");
				long low = Integer.parseInt(temp[0]);
				long high = Integer.parseInt(temp[1]);
				long answer = 0;
				answer = Math.max(a, b) * (high / lcm - low / lcm + 1);
				if(answer - low - ((low / lcm) * lcm) < 0)
					answer -= Math.max(a, b);
				else
					answer -= low - ((low / lcm) * lcm);
				if(Math.max(a, b) - ((high + 1) - ((high / lcm) * lcm)) > 0)
					answer -= Math.max(a, b) - ((high + 1) - ((high / lcm) * lcm));
				if(i == 0)
					System.out.print((high - low + 1) - answer);
				else
					System.out.print(" " + ((high - low + 1) - answer));
			}
			System.out.println();
		}
	}
	private static int findLCM(int min, int max)
	{
		int temp = max;
		while(temp % min != 0)
			temp += max;
		return temp;
	}
}