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 
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T a,Args... args) {cout<<a<<' ';debug(args...);}
#define fore(i,a,b) for(int i=a,gon=b;i<gon;++i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    #ifdef LOCAL
        //freopen("in.txt", "r", stdin);
    #else
    	#define endl '\n'
    #endif
    int t;
    cin >> t;
    while (t--) {
        ll a, b, q;
        cin >> a >> b >> q;
        if (a > b) swap(a, b);
        while (q--) {
            ll l, r;
            cin >> l >> r;
            if (b%a == 0) {
                cout << "0 ";
            } else {
                l = max(l, b);
                if (r < l) cout << "0 ";
                else {
                	ll lcm = a/__gcd(a, b) * b;
                	ll cnt = r/lcm - (l-1)/lcm;
                	cnt *= b;
                	if (r%lcm) {
                		ll i = (r/lcm+1)*lcm-b+a;
                		for (; i <= r; i++) cnt--;
                	}
            		ll i = (l+lcm-1)/lcm*lcm-b+a;
            		for (; i < l; i++) cnt++;
                	cout << r-l+1-cnt << " ";
                }
            }
        }
        cout << endl;
    }
}
