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:
import java.io.*;
import java.util.*;

public class A
{
    static int a, b, q;
    static long l, r;
    static long[] cnt;
    static char[] s;
    public static void main(String[] args) throws IOException
    {
        Flash f = new Flash();
        int T = f.ni();
        for(int tc = 1; tc <= T; tc++){
            a = f.ni(); b = f.ni(); q = f.ni();
            calc();
            long[] ans = new long[q];
            for(int i = 0; i < q; i++){
                l = f.nl(); r = f.nl();
                ans[i] = fn();
            }
            
            print(ans);
        }
    }
    
    static void calc(){
        int lcm = (a*b)/gcd(a, b);
        cnt = new long[lcm+1];
        cnt[0] = 0;
        for(int i = 1; i <= lcm; i++){
            cnt[i] = cnt[i-1];
            if((i%a)%b != (i%b)%a) cnt[i]++;
        }
    }
    
    //any common multiple will never satisfy the given equation.
    //very obvious common multiple is a*b
    //let x = a*b
    //(x%a)%b = (x%b)%a = 0
    //but (x%a)%b should be not equal to (x%b)%a
    //a and b are very small
    //so we can simply find the cnt for [0, lcm] and find cnt for every range till R and 
    //similarly find for (L-1), then subtract ans(L-1) from ans(R)
    static long fn()
    {
        int lcm = (a*b)/gcd(a, b);
        
        long ans = 0;
        long seg = r/lcm;
        long rem = r%lcm;
        ans += cnt[lcm]*seg + cnt[(int)rem];
        
        seg = (l-1)/lcm;
        rem = (l-1)%lcm;
        ans -= cnt[lcm]*seg + cnt[(int)rem];
        
        return ans;
    }
    
    static int gcd(int a, int b){
        if(a == 0) return b;
        if(b == 0) return a;
        
        if(a <= b) return gcd(b%a, a);
        return gcd(a%b, b);
    }
    
    static void sort(int[] a){
        List<Integer> A = new ArrayList<>();
        for(int i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static int swap(int itself, int dummy){
        return itself;
    }
    
    static void sop(Object o){ System.out.println(o); }
    
    static void print(long[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        System.out.println(sb);
    }
    
    static class Flash
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next(){
            while(!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            
            return st.nextToken();
        }
        
        String ns(){
            String s = new String();
            try{
                s = br.readLine().trim();
            }catch(IOException e){
                e.printStackTrace();
            }
            
            return s;
        }
        
        int ni(){
            return Integer.parseInt(next());
        }
        
        int[] arr(int n){
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

        long nl(){
            return Long.parseLong(next());
        }
        
        double nd(){
            return Double.parseDouble(next());
        }
    }
}