You have just got the best gift ever, a Pogo stick. The pogo stick is something you use to jump off the ground while standing on it.
This Pogo stick is a special one: the first jump will move you a distance of unit, the second jump will move you units, the third jump will move you units and so on. You can jump in only four directions using this stick: north (increasing ), south (decreasing ), east (increasing ) or west (decreasing ).
Now you want to play a game in your backyard, which we model as an infinite plane. You are standing with your stick in at point and you want to go to point .
The point will never be , and it will always be reachable from your starting point.
Check the output section carefully, because the required outputs for the small and large datasets are not the same.
输入格式
The first line of the input gives the number of test cases, . test cases follow, one per line. Each line consists of integers separated by a single space, and , the coordinates of the point you want to reach.
输出格式
For each test case, output one line containing "Case #x: y", where is the case number (starting from ) and is a string represents the directions of the moves, for example if you are going to move north then south then east then west, this string should be NSEW.
For the small dataset, the output is considered correct if it does not take more than moves to reach the destination in each test case.
For the large dataset, the output is considered correct if it reaches the destination point in the minimum possible number of moves.
If there are multiple correct solutions, print any of them.
样例
样例输入 1
2
3 4
-3 4
样例输出 1
Case #1: ENWSEN
Case #2: ENSWN
数据范围与提示
Sample Explanation
The output for the first sample test case will not be considered correct if it is in the large dataset, because the number of moves is not the minimum. WNSEN would be a correct output for this test case if it were in the large dataset.
