Mandy and brz are traveling in a country that can be described by a two-dimensional plane. The country's $x$-boundaries are $-10^3$ and $3 \times 10^3$, and the $y$-boundaries are $-10^3$ and $3 \times 10^3$. This means both can only move within the range $x, y \in [-10^3, 3 \times 10^3]$; they are not allowed to leave the country's boundaries.

There is an old and romantic tradition in this country: if you love someone, you should give them a favorite number. Mandy has already chosen a number, and is waiting for brz at one location in the country, while brz is holding an initial number at another location. This number is not necessarily the one Mandy wants. To accurately deliver the number to Mandy, brz must go through a ritual, and the ritual is called "Precise Romance."

During the ritual, brz can move. Each move consists of moving one unit in the up, down, left, or right direction, and the number in brz's hand will change due to the power of the ritual. Assuming brz's current coordinate is $(x, y)$, the changes are as follows:

1. Move left: The coordinate becomes $(x - 1, y)$, and the number in brz's hand becomes $-1$.
2. Move right: The coordinate becomes $(x + 1, y)$, and the number in brz's hand becomes $+1$.
3. Move up: The coordinate becomes $(x, y + 1)$, and the number in brz's hand becomes $\times 2$.
4. Move down: The coordinate becomes $(x, y - 1)$, and the number in brz's hand becomes $\div 2$ (rounded towards zero).

brz's final goal is to reach the location where Mandy is, and at this time, the number in his hand must be the same as the one Mandy desires. Then, brz can deliver his "Precise Romance."

In addition, the ritual has the following extra constraints:

• The initial positions of brz and Mandy must satisfy $x, y \in [0, 2 \times 10^3]$. During the movement, brz can leave this range, but he cannot leave the country's boundaries.
• During the ritual, the number in his hand can change, but its absolute value must be kept less than or equal to $10^9$, otherwise the number will exceed the ritual's capacity and the ritual will fail.
• The total path length of brz's movement cannot exceed $5 \times 10^3$ units, meaning he can only move at most this many steps.

One more thing to add: brz can pass through the location where Mandy is without delivering the number; he only needs to deliver it at the end of the ritual.

brz has already planned a route, but he is now testing you. Can you find a route that allows brz to deliver his "Precise Romance"?

Input

The first line contains an integer $T$ ($1 \le T \le 100$), representing the number of test cases.

For each test case, there is a single line containing six integers $S_x, S_y, T_x, T_y, x, y$ ($0 \le S_x, S_y, T_x, T_y \le 2 \times 10^3$, $1 \le x, y \le 10^9$), where $(S_x, S_y)$ is brz's initial position, $(T_x, T_y)$ is Mandy's position, $x$ is the initial number in brz's hand, and $y$ is the number Mandy expects.

Output

For each test case, output a single line consisting of a string of WASD representing brz's movement path. The string represents the sequence of moves: W for moving one unit up, A for moving one unit left, S for moving one unit down, and D for moving one unit right.

If there are multiple valid paths, output any one of them.

Examples

Input 1

3
1 1 2 2 2 5
2 2 1 1 6 2
1 1 3 1 1 2

Output 1

WD
SA
DDADAWDDSA