This problem is a programming version of Problem 220 from projecteuler.net
Let be the two-letter string "Fa". For , derive from by the string-rewriting rules:
Thus, = "Fa", = "FaRbFR", = "FaRbFRRLFaLbFR", and so on.
These strings can be interpreted as instructions to a computer graphics program, with "F" meaning "draw forward one unit", "L" meaning "turn left degrees", "R" meaning "turn right degrees", and "a" and "b" being ignored. The initial position of the computer cursor is , pointing up towards .
Then is an exotic drawing known as the of order . For example, is shown below; counting each "F" as one step, the highlighted spot at is the position reached after steps.
What is the position of the cursor after "F"-steps in ?
Input Format
First line of each test file contains a single integer that is the number of queries per test file. blocks of lines follow, the first of which contains a single integer and the second contains a single integer . Note, that while is given in decimal, is given in hexadecimal.
Constraints
- Sum of all per test file
- number of moves in
- All characters in representation of m are in
Output Format
Print exactly two lines per each query. In the first line print the x-coordinate of the cursor and in the second line print the y-coordinate of the cursor. As from input, these numbers should also be in hexadecimal.