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.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scn=new Scanner(System.in);
        int T=scn.nextInt();
        for(int t=0;t<T;t++)
        {
            int a=scn.nextInt(), b=scn.nextInt(), q=scn.nextInt();
            int lcm=a*b/HCF(a,b);
            AB[] queries=new AB[q];
            for(int i=0;i<q;i++){
                queries[i]=new AB(scn.nextLong(), scn.nextLong());
            }
            int[] xmodamodb=new int[lcm+1];
            int[] xmodbmoda=new int[lcm+1];
            int max=Math.max(a, b);
            for(int i=1;i<=lcm;i++){
                xmodamodb[i]=(max%a)%b;
                xmodbmoda[i]=(max%b)%a;
                max++;
            }
            int[] prefixCount=new int[lcm+1];
            int prefix=0;
            for(int i=1;i<=lcm;i++){
                if(xmodamodb[i]!=xmodbmoda[i]){
                    prefix++;
                }
                prefixCount[i]=prefix;
            }
            for(int i=0;i<q;i++){
                long l=queries[i].l;
                long r=queries[i].r;
                long ans=0;
                if(r>=Math.max(a,b)){
                    ans=prefixCount[(int) ((r-Math.max(a,b)+1)%lcm)]+((r-Math.max(a,b))/lcm)*prefixCount[lcm];
                }
                if(l>=Math.max(a,b)){
                    ans=ans - prefixCount[(int) ((l-Math.max(a,b))%lcm)]-((l-Math.max(a,b))/lcm)*prefixCount[lcm];
                }
                System.out.print(ans+" ");

            }
            System.out.println();

        }
    }

    private static int HCF(int a, int b) {
        if(b>a){
         if(b%a==0){
             return a;
         }
         else{
             return HCF(b%a, a);
         }
        }
        else{
            if(a%b==0){
                return b;
            }
            else{
                return HCF(b, a%b);
            }
        }
    }

    static class AB{
        long l,r;
        AB(long a, long b){
            this.l=a;
            this.r=b;
        }
    }
}
