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.util.function.Function;
import java.util.stream.Collectors;
import java.io.*;
import java.math.*;
public class Main7
{
	static class Pair
	{
		int x;
		int y;
		Pair(int x,int y)
		{
			this.x=x;
			this.y=y;
		}
	}
	static int mod=998244353;
	public static int[] sort(int[] a)
	{
		int n=a.length;
		ArrayList<Integer> ar=new ArrayList<>();
		for(int i=0;i<a.length;i++)
		{
			ar.add(a[i]);
		}
		Collections.sort(ar);
		for(int i=0;i<n;i++)
		{
			a[i]=ar.get(i);
		}
		return a;
	}
	public static int pow(int a, int b)
    {
        int result=1;
        while(b>0)
        {
            if (b % 2 != 0)
            {
                result=(result*a)%mod;
                b--;
            } 
            a=(a*a)%mod;
            b /= 2;
        }   
        return result;
    }
	
    public static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b%a, a);
    }   
	public static long lcm(long a, long b)
	{
		return a*(b/gcd(a,b));
	}
	static ArrayList<ArrayList<Integer>> graph;
	static public void main(String args[])throws IOException
	{
		int tt=i();
		StringBuilder sb1=new StringBuilder();
		for(int ttt=1;ttt<=tt;ttt++)
		{
			int a=i();
			int b=i();
			int q=i();
			int pp=0;
			/*for(int i=999;i<=1000;i++)
			{
				int num1=(i%a)%b;
				int num2=(i%b)%a;
				if(num1==num2)
				{
					pp++;
				}
			}
			pln(pp+"");
			*/long lcm=lcm(a,b);
			int min=Math.min(a,b);
			int max=Math.max(a,b);
			for(int i=0;i<q;i++)
			{
				long l=l();
				long r=l();
				long range=r-l+1;
				if(a==b)
				{
					sb1.append("0 ");
					continue;
				}
				long ans=0;
				if(max-1>=r)
				{
					ans=r-l+1;
				}
				else if(max-1>=l && max-1<=r)
				{
					ans=ans+(max-1)-l+1;
				}
				if(lcm>=l && lcm<=r)
				{
					l=lcm;
					long ans1=0;
					long tmp=r/lcm;
					long tmp1=l/lcm;
					if(l%lcm==0 && r%lcm==0)
					{
						ans1=tmp-tmp1+1;
					}
					else if(l%lcm!=0 && r%lcm==0)
					{
						ans1=tmp-tmp1;
					}
					else if(l%lcm==0 && r%lcm!=0)
					{
						ans1=tmp-tmp1+1;
					}
					else
					{
						ans1=tmp-tmp1;
					}
					if(ans1>1)
					{
						ans=ans+(ans1-1)*max;
						long yy=tmp*lcm;
						if(yy+max-1<=r)
							ans=ans+max;
						else
							ans=ans+(r-yy+1);
					}
					else if(ans1==0)
					{
						
					}
					else if(ans1==1)
					{
						long yy=tmp*lcm;
						if(yy+max-1<=r)
							ans+=max;
						else
							ans=ans+(r-yy+1);
					}
				}
				else if(lcm>r)
				{
					
				}
				else if(lcm<l)
				{
					long ans1=0;
					long tmp=r/lcm;
					long tmp1=l/lcm;
					if(l%lcm==0 && r%lcm==0)
					{
						ans1=tmp-tmp1+1;
					}
					else if(l%lcm!=0 && r%lcm==0)
					{
						ans1=tmp-tmp1;
					}
					else if(l%lcm==0 && r%lcm!=0)
					{
						ans1=tmp-tmp1+1;
					}
					else
					{
						ans1=tmp-tmp1;
					}
					if(ans1>1)
					{
						ans=ans+(ans1-1)*max;
						long yy=tmp*lcm;
						if(yy+max-1<=r)
							ans=ans+max;
						else
							ans=ans+(r-yy+1);
					}
					else if(ans1==0)
					{
						
					}
					else if(ans1==1)
					{
						long yy=tmp*lcm;
						if(yy+max-1<=r)
							ans+=max;
						else
							ans=ans+(r-yy+1);
					}
				}
				sb1.append((range-ans)+" ");
			}
			sb1.append("\n");
		}	
		System.out.print(sb1.toString());
	}
	/**/
	static InputReader in=new InputReader(System.in);
	static OutputWriter out=new OutputWriter(System.out);
	public static long l()
	{
		String s=in.String();
		return Long.parseLong(s);
	}
	public static void pln(String value)
	{
		System.out.println(value);
	}
	public static int i()
	{
		return in.Int();
	}
	public static String s()
	{
		return in.String();
	}
}
	class InputReader 
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
	 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
	 
		public int read() {
			if (numChars== -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	 
		public int Int() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	 
		public String String() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
	 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	 
		public String next() {
			return String();
		}
	 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
	 
	class OutputWriter {
		private final PrintWriter writer;
	 
		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}
	 
		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}
	 
		public void print(Object...objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}
	 
		public void printLine(Object...objects) {
			print(objects);
			writer.println();
		}
	 
		public void close() {
			writer.close();
		}
	 
		public void flush() {
			writer.flush();
		}
	 
		}
	 
		class IOUtils {
	 
		public static int[] readIntArray(InputReader in, int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = in.Int();
			return array;
		}
	 
	} 

