Treasure Location

Define the function dig as follows.

• If 0 <= x <= 9, then dig(x) = x.
• If x >= 10, then dig(x) is found by summing the digits of x and applying dig again to that sum.

For example, dig(49) = dig(13) = dig(4) = 4.

Minsik is following an old map to find a treasure. He starts at coordinate (0, 0) facing north. North is the direction in which the Y-coordinate increases, and east is the direction in which the X-coordinate increases.

The gold number is initially 1. Minsik repeats the following process K times.

1. Move forward by dig of the current gold number, then turn 90 degrees to the right.
2. Multiply the gold number by M.

Find the position after K repetitions, which is the coordinate of the treasure.

The first line contains the number of test cases, T. Each of the next T lines contains two natural numbers K and M for one test case.

• 1 <= K <= 10^9
• 1 <= M <= 1000

For each test case, output the treasure location in the form X Y on its own line.