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

public class Solution{
  public static void main(String[] args) throws IOException{
    StringBuilder print = new StringBuilder();
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(input.readLine());
    while(t-- > 0){
      StringTokenizer st = new StringTokenizer(input.readLine());
      long a = Long.parseLong(st.nextToken());
      long b = Long.parseLong(st.nextToken());
      long tempA = a;
      long tempB = b;
      long q = Long.parseLong(st.nextToken());
      long lcm = 1;
      for(int prime = 2; prime < 15; prime++){
        boolean divide = true;
        while(divide){
          if( tempA%prime != 0 ){
            divide = false;
          }
          if( tempB%prime != 0){
            divide = false;;
          }
          if(divide){
            tempA /= prime;
            tempB /= prime;
            lcm *= prime;
          }
        }
      }
      lcm = (a * b)/lcm;
      long total = 0;
      ArrayList<Long> totalList = new ArrayList<Long>();
      for(int j = 0; j < lcm; j++){
        if(((j%b)%a) != ((j%a)%b)){
          total++;
        }
        totalList.add(total);
      }

      long period = Math.min(a,b);
      for(long i = 0; i < q; i++){
        st = new StringTokenizer(input.readLine());
        long l = Long.parseLong(st.nextToken());
        long r = Long.parseLong(st.nextToken());

        long firstPeriod = l/lcm;
        long lastPeriod = r/lcm;
        long totalPeriodValue = (lastPeriod - firstPeriod + 1) * total;
        long subtractL = l%lcm;
        if(subtractL != 0){
          subtractL = totalList.get((int)(subtractL - 1));
        }
        long subtractR = total - totalList.get((int)(r%lcm));
        //System.out.printf("firstPeriod: %d, lastPeriod: %d, totalPeriodValue: %d, subLeft: %d, subRight: %d%n", firstPeriod, lastPeriod, totalPeriodValue, subtractL, subtractR);
        print.append(totalPeriodValue - subtractL - subtractR + " ");
      }
      print.append("\n");
    }
    System.out.println(print.toString());
  }
}