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:
/* package codechef; // don't place package name! */

import java.lang.*;
import java.io.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastReader sc = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int test = sc.nextInt();
		while(test-->0)
		{
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    int lcm = (a*b)/gcd(a,b);
		    int max=Math.max(a,b);
		    int q = sc.nextInt();
		    while(q-->0)
		    {
		        long l = sc.nextLong();
		        long r = sc.nextLong();
		        long total=r-l+1;
		        long multiples=(r/lcm)-((l-1)/lcm);
		        long ans = total-multiples*max;
		        long lastMultiple=(r/lcm)*lcm;
		        long firstMultiple=((l-1)/lcm)*lcm;
		        if(l>=lcm && l<=firstMultiple+max-1) ans=ans-(firstMultiple+max-l);
		        if(r>=lcm && lastMultiple+max-1>r) ans=ans+lastMultiple+max-1-r;
		        if(l<max) ans=ans-(max-l);
		        if(r<max) ans=ans+max-r-1;
		        out.print(ans +" ");
		    }
		    out.println();
		}
		
		
		out.close();
	}
	static int gcd(int a, int b) 
    { 
        if (b == 0) 
            return a; 
        return gcd(b, a % b);  
      
    }
}

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; 
    } 
}