1399번 - 보물의 위치

dig라는 함수를 다음과 같이 정의하자.

• dig(x) = x (0 ≤ x ≤ 9)
• dig(x) = dig(x의 모든 자리수의 합) (x ≥ 10)

예를 들어, dig(49) = dig(13) = dig(4) = 4

오민식은 아주 낡은 지도를 가지고 보물을 찾아 헤매는 사냥꾼의 두목이다. 낡은 지도에는 보물을 어떻게 찾아야 하는지가 나와 있다.

지금 오민식은 북쪽을 보고 있고, 현재 좌표는 (0, 0)이다. 북쪽은 Y좌표가 증가하는 방향, 동쪽은 X좌표가 증가하는 방향이다.

오민식은 다음과 같은 작업을 K번 반복하면 보물의 위치를 찾을 수 있다. 골드 넘버는 1부터 시작한다.

1. dig(골드 넘버)만큼 앞으로 간다. 그리고 90도 오른쪽으로 회전한다.
2. 골드 넘버에 M을 곱한다.

오민식의 마지막 위치. 즉, 보물의 위치를 출력하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 각각의 테스트 케이스에 대해  K와 M이 주어진다. K는 10⁹보다 작거나 같은 자연수이고, M은 1000보다 작거나 같은 자연수이다.

각각의 테스트 케이스에 대해 보물의 위치를 X Y 형태로 출력한다.