Let f(A, B), where A and B are positive integers, be the string satisfying the following conditions:

* f(A, B) has length A + B;
* f(A, B) contains exactly A letters `A` and exactly B letters `B`;
* The length of the longest substring of f(A, B) consisting of equal letters (ex., `AAAAA` or `BBBB`) is as small as possible under the conditions above;
* f(A, B) is the lexicographically smallest string satisfying the conditions above.



For example, f(2, 3) = `BABAB`, and f(6, 4) = `AABAABAABB`.

Answer Q queries: find the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Constraints

* 1 \leq Q \leq 10^3
* 1 \leq A_i, B_i \leq 5 \times 10^8
* 1 \leq C_i \leq D_i \leq A_i + B_i
* D_i - C_i + 1 \leq 100
* All input values are integers.

Input

Input is given from Standard Input in the following format:


Q
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_Q B_Q C_Q D_Q


Output

For each query i in order of input, print a line containing the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Example

Input

5
2 3 1 5
6 4 1 10
2 3 4 4
6 4 3 7
8 10 5 8


Output

BABAB
AABAABAABB
A
BAABA
ABAB
#include<bits/stdc++.h>
using namespace std;
int T,a,b,c,d,k,l,r,ca,cb,mid,o,n;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d %d %d %d",&a,&b,&c,&d);
		n=a+b;
		k=max(a,b)/(min(a,b)+1)+(max(a,b)%(min(a,b)+1)==0?0:1);
		l=0,r=n+1;
		while (r>l)
		{
			mid=l+r>>1;
			ca=a-mid/(k+1)*k-mid%(k+1);
			cb=b-mid/(k+1);
			if (1ll*cb<=1ll*k*ca)l=mid+1;else r=mid;
		}
		ca=a-l/(k+1)*k-l%(k+1);
		cb=b-l/(k+1);
		o=l+cb-ca*k+1;
		for (int i=c;i<=min(d,l);i++)printf("%c",i%(k+1)!=0?'A':'B');
		for (int i=max(c,l+1);i<=d;i++)printf("%c",(i-o)%(k+1)!=0?'B':'A');
		printf("\n");
	}
}