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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {
	static class FastReader
	{
	  BufferedReader br;
	  StringTokenizer st;

	  public FastReader()
	  {
	    br = new BufferedReader(new
	            InputStreamReader(System.in));
	  }

	  String next()
	  {
	    while (st == null || !st.hasMoreElements())
	    {
	      try
	      {
	        st = new StringTokenizer(br.readLine());
	      }
	      catch (IOException  e)
	      {
	        e.printStackTrace();
	      }
	    }
	    return st.nextToken();
	  }

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

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

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

	  String nextLine()
	  {
	    String str = "";
	    try
	    {
	      str = br.readLine();
	    }
	    catch (IOException e)
	    {
	      e.printStackTrace();
	    }
	    return str;
	  }
	}
	
  public static void main(String[] args){
	int t;
	FastReader fr = new FastReader();
	t = fr.nextInt();
	for (int i = 0; i < t; ++i) {
		long a, b, q;
		a = fr.nextLong();
		b = fr.nextLong();
		q = fr.nextLong();
		long minVal = Long.min(a,b);
		long maxVal = Long.max(a,b);
		int[][] counts = new int[(int)minVal][(int)maxVal];
		for(int coun = 0; coun < minVal * maxVal; ++coun) {
			int j = (int) (coun % minVal);
			int k = (int) (coun % maxVal);
			if((j % minVal) % maxVal != ((k % maxVal) % minVal)) {
				counts[j][k] = counts[(j+(int)minVal-1)%(int)minVal][(k+(int)maxVal-1)%(int)maxVal] + 1;
			} else {
				counts[j][k] = counts[(j+(int)minVal-1)%(int)minVal][(k+(int)maxVal-1)%(int)maxVal];
			}
		}
		for (int j = 0; j < q; ++j) {
			long l = fr.nextLong();
			long r = fr.nextLong();
			long total_amount_cycle = counts[(int)minVal - 1][(int)maxVal -1];
			long cycle_length = minVal * maxVal;
			long res = (total_amount_cycle - counts[(int)((l-1)%minVal)][(int)((l-1)%maxVal)]) + counts[(int)(r % minVal)][(int)(r % maxVal)];
			long full_cycles = (r - (r % cycle_length) - 1 - (l + cycle_length - (l % cycle_length))) / cycle_length;
			res += total_amount_cycle * full_cycles;
			System.out.print(res + " ");
		}
		System.out.println("");
	}
  }
}

