이진트리(Binary Tree)

프로그램 명: binary_tree

제한시간: 1 초

이진 트리는 컴퓨터 사이언스에 자주 사용하는 자료 구조이다.

이 문제에서는 한 노드가 2 개의 정수를 가지는 무한 이진트리에 대해서 생각한다.

문제에서의 트리는 다음과 같은 구조로 되어 있다:

(a,b) 를 가지는 노드가 주어질 때 , 루트 노드에서 주어진 노드까지 가장 가까운 길로 갈 때 왼쪽 자식으로 가는 길의 횟수가 얼마인지 오른쪽 자식으로 가는 길의 횟수가 얼마인지를 찾는 것이다.

첫 줄은 테스트 데이터의 수 이다.

각 테스트 데이터는 두 개의 정수 i , j ( 1 <= i , j <= 2*10^9) 가 주어진다. 이는 노드(i,j) 를 의미한다. i,j 값은 위에서 정의한 트리에서 유효한 값이 입력으로 주어진다.

각 입력데이터의 대해서 출력 예의 형식으로 출력한다.

출력의 첫 수는 왼쪽 자식으로 가는 횟수이고 다음 수는 오른쪽으로 가는 길의 횟수이다. 각 출력 후 한 줄의 빈줄을 준 후 다음 데이터의 결과를 출력한다.

입력

3
42 1
3 4
17 73

출력

Scenario #1:
41 0

Scenario #2:
2 1

Scenario #3:
4 6

출처: TUD Programming Contest 2005 (Training Session), Darmstadt, Germany