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;
#define ll long long
#define ld long double
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define here(x) cout << #x << " = " << x << endl;
#define show(x) {for( auto ii : x) cout << ii << setw(6); cout << endl;}
#define shop(n, x) {for(int i = 0; i < n; i++) cout << x << setw(6); cout << endl;}
#define ff first
#define ss second
#define endl '\n'
#define en " "
#define pb push_back
#define mpair make_pair
ll mod = 1000000007;
ll inf = LLONG_MAX;
long double pi = 3.1415926536;
int main()
{
	fastio();
	int tt = 1;
	cin >> tt;
	while(tt--)
	{
		// 		j NOT i 		check		//		CHECK -> if()   else if()
		ll n, x = 0, m = 0, y = 0, k = inf;
		ll a, b, q;
		cin >> a >> b >> q;
		m = (a * b) / (__gcd(a, b));
		if(a > b)
			swap(a, b);
		while(q--)
		{
			ll l, r;
			cin >> l >> r;
			
			if(r < b || (b % a == 0))
			{
				cout << 0 << en;
				continue;
			}		
			x = r / m;
			y = l / m;
			k = (x - y) * b;
			if(x != y)
			{
				k = (x - y - 1) * b;
				ll p = r - x * m;
				k += min(p + 1, b);
			}
			// here(x << en << y)
			cout << r - max(l, b) - k + 1 << en;
		}
		cout << endl;
	}
}