C. Yet Another Counting Problem

You are given two integers a and b, and q queries. The i-th query consists of two numbers li and ri, and the answer to it is the number of integers x such that $li≤x≤ri$, and $((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod 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 li and ri $(1≤li≤ri≤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

1
2
3
4
5
6
7
8
9
10
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200

output

1
2
0 0 0 2 4 
0 91

$((x \bmod a) \bmod b) , ((x \bmod b) \bmod a)$ 的值以 lcm(a,b) 周期性变化。统计每一个周期中不一样的个数 cnt

对于一个数 x , (x/k) * cnt + f[x % k] = ans;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int t;
ll l,r,a,b,q,f[50000];
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
ll lcm(ll a, ll b){
	return a*b / gcd(a,b);
}
int main(){
	//freopen("in","r",stdin);
	sf(t);
	while(t--){
		scanf("%lld%lld%lld",&a,&b,&q); 
		ll k =lcm(a,b);
		ll cnt =0;
		f[0]=0;
		fi(i,1,k+1)
			if((i%a)%b != (i%b)%a) {
				cnt ++;
				f[i]=f[i-1]+1;
			}else f[i]=f[i-1];
		while(q--){
			scanf("%lld%lld",&l,&r); 
			ll ans=0;
			if(a==b) {
				pfc("0 ");continue;
			}
			ans = ((r/k) * cnt + f[r%k]) - (((l-1)/k) * cnt + f[(l-1)%k]);
			printf("%lld ",ans);
		}
		pfc("\n");
	}
	return 0;
}