C :: Soo, The Gamer

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Soo decides to play a game with Nahaal. Initially, they place some random digits (0-1…9) one after another to make a long string of digits. Then, each player choose an arbitrary number (a and b) less than 108 and start the game. The game is played with the following rules: 

1. Soo is the first player (round 1); 

2. During each round the player who is on her turn, will cut the string of digits into two nonempty parts based on the round number, r, as index. For example, string 1234 on round 2 is splitting to numbers 12 and 34. 

3. If the first (left) part is divisible by a, and the second (right) part is divisible by b, the player wins! Note that both parts should be positive integers that have no leading zeros. Otherwise, they go to round r+1 and swap the turn. 

Your task is to write a program to determine which player can win the game at first. 

Input

In the first line of input there is T, number of test-cases. 

Each test case, start with a line containing the initial string of digits, “S”, without leading zeroes. It's guaranteed that 1 ≤ len(S) ≤ 10⁶ .The next line, contains a pair of space-separated positive integers a, b (1 ≤ a, b ≤ 10⁸). 

Output

For each test case, in the first line print the name of the winner,”Soo” or “Nahaal” (without the quotes), if there is one! Next, print the left and right parts after the successful cut, each in a single line. These two parts, being concatenated, must be exactly identical to the initial string. The left part must be divisible by a, and the right part must be divisible by b. The two parts must be positive integers having no leading zeroes. If there is no winner, print in a single line "DRAW" (without the quotes). 

Sample Input

3
302
3 2
23
2 3
23
2 2

Sample Output

Nahaal
30
2
Soo
2
3
DRAW

Submit

Source: 13th Iran Nationwide Internet Contest - Isfahan