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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class C
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         while(T-->0)
         {
            st = new StringTokenizer(infile.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            if(A > B)
            {
               int t = A;
               A = B;
               B = t;
            }
            int lcm = (A*B)/((int)gcd(A,B));
            long cnt = 0L;
            pref = new long[lcm];
            for(int x=B; x < lcm; x++)
            {
               pref[x] += pref[x-1];
               int a = (x%B)%A;
               int b = (x%A)%B;
               if(a != b)
               {
                  pref[x]++;
                  cnt++;
               }
            }
            int Q = Integer.parseInt(st.nextToken());
            while(Q-->0)
            {
               st = new StringTokenizer(infile.readLine());
               long L = Long.parseLong(st.nextToken());
               long R = Long.parseLong(st.nextToken());
               long res = solve(R, cnt, A, B)-solve(L-1, cnt, A, B);
               sb.append(res+" ");
            }
            sb.append("\n");
         }
         System.out.print(sb);
      }
      static long[] pref;
      public static long solve(long R, long cnt, int A, int B)
      {
         int lcm = (A*B)/((int)gcd(A,B));
         long res = cnt*(R/lcm);
         long temp = R%lcm;
         if(temp >= B)
            res += pref[(int)temp]-pref[B-1];
         return res;
      }
      public static long gcd(long a, long b)
      {
         if(a > b)
         {
            long t = a;
            a = b;
            b = t;
         }
         if(a == 0L)
            return b;
         return gcd(b%a, a);
      }
   }