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;
typedef long long int ll;

void solve()
{
	ll a,b,q;
	cin>>a>>b>>q;
	ll lcm = a*b/(__gcd(a,b));
	ll pre[lcm];
	pre[0] = 0;
	for (int i = 1; i < lcm; ++i)
	{
		/* code */
		if(i<max(a,b))
			pre[i] = pre[i-1];
		else
			pre[i] = pre[i-1]+1;
	}
	while(q--)
	{
		ll l,r;
		cin>>l>>r;
		// if(r<max(a,b))
		// {
		// 	cout<<"0 ";
		// 	continue;
		// }
		// ll ol = l;
		// if(l<max(a,b))
		// 	l = max(a,b);
		// ll ans = r-l+1;
		// // ans -= (ans)/lcm;
		// ll t = r-ol+1;
		// // ans -= t/a +t/b;
		// ll k = (ans/lcm)*lcm;
		// // if(r>lcm)
		// // if(r-k>min(a,b))
		// // 	ans-=a;
		// // else
		// // 	ans-=r-k;
		// ans -= (max(a,b))*(max(0ll,t/(lcm)-1));

		// if(k!=0)
		// {
		// if(r-k+1>max(a,b))
		// 	ans -= max(a,b);
		// else if(r-k+1>0)
		// {
		// 	ans -= r-k+1;
		// }
		// }
		// ll y = 
		// cout<<ans<<" ";

		ll l1 = (l/lcm+1)*lcm;
		ll r1 = (r/lcm)*lcm;
		ll ans = max(r1-l1,0ll);
		ans -= (max(a,b))*(max(0ll,(r1-l1)/(lcm)));
		if(l1>r1)
		{
			// for(ll i = l; i<=r; i++)
			// 	if(i%lcm>=max(a,b))
			// 		ans++;
			ans += pre[r%lcm]-pre[(l-1+lcm)%lcm];
		}
		else
		{
			// for(ll i = l; i<l1;i++)
			// {
			// 	if(i%lcm>=max(a,b))
			// 		ans++;
			// }
			
			// for(ll i = r1; i<=r;i++)
			// {
			// 	if(i%lcm>=max(a,b))
			// 		ans++;
			// }
			ans += pre[lcm-1]-pre[(l-1+lcm)%lcm]+pre[r%lcm];
		}
		
		
		cout<<ans<<" ";
	}
	cout<<endl;
}

int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}