보물의 위치

함수 dig를 다음과 같이 정의한다.

• 0 <= x <= 9이면 dig(x) = x이다.
• x >= 10이면 dig(x)는 x의 각 자리 숫자의 합에 다시 dig를 적용한 값이다.

예를 들어 dig(49) = dig(13) = dig(4) = 4이다.

민식은 오래된 지도를 따라 보물을 찾고 있다. 처음에는 좌표 (0, 0)에 있고 북쪽을 바라본다. 북쪽은 Y좌표가 증가하는 방향이고, 동쪽은 X좌표가 증가하는 방향이다.

골드 넘버는 처음에 1이다. 민식은 다음 과정을 K번 반복한다.

1. 현재 골드 넘버의 dig 값만큼 앞으로 이동한 뒤, 오른쪽으로 90도 회전한다.
2. 골드 넘버에 M을 곱한다.

K번 반복한 뒤의 위치, 즉 보물의 좌표를 구하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 T개의 줄에는 각각 하나의 테스트 케이스를 나타내는 자연수 K와 M이 주어진다.

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

각 테스트 케이스마다 보물의 위치를 X Y 형식으로 한 줄에 출력한다.