주행시험장

• 가장 일반적인 케이스를 생각해보면, m>=n 일때, k=n+1로 잡는것으로 모든 차를 옮길수 있다.
  • 동쪽에서 서쪽으로 갈때는 전방차 n대 + 코너차 1대를 옮기고, 서쪽에서 동쪽으로 돌아올때는 전방차 n대만 갖고 오는 것을 반복하면, 한번 반복 할때마다 동쪽에 있는 코너차가 1대씩 서쪽으로 옮겨지게 된다. 동쪽에 코너차가 n+1대가 남게 되면, 이번에는 코너차 n+1대를 서쪽으로 가져가고 빈손으로 동쪽으로 돌아온 뒤에, 전방차n대를 서쪽으로 옮겨가는 것으로 작업이 마무리된다.
• 그래서 k=n+1이면 어떤 경우에나 옮길수 있다는 것은 알겠는데, 이제 케이스를 나눠서 더 최적으로 옮길수 있는 케이스들을 찾아야 한다.
• m=n 이라면, k=n으로 잡고, 3번만에 옮길수 있다.
  • 0: (0,0) | (m,n)*
  • 1: (m,0)*| (0,n)
  • 2: (m,0) | (0,n)*
  • 3: (m,n)*| (0,0)
• m≤2n 이라면, k=n으로 잡고, 7번만에 옮길수 있다.
  • 0: (0,0) | (m,n)*
  • 1: (0,n)*| (m,0)
  • 2: (0,n) | (m,0)*
  • 3: (n,n)*| (m-n,0)
  • 4: (n,0) | (m-n,n)*
  • 5: (m,0)*| (0,n)
  • 6: (m,0) | (0,n)*
  • 7: (m,n)*| (0,0)
• 나머지 경우에는 k=n+1로 잡아야만 한다.
• m≤n+2 인 경우에는 k=n+1로 잡고 5번만에 옮길수 있다.
  • 0: (0,0) | (m,n)*
  • 1: (0,n)*. | (m,0)
  • 2: (0,n) | (m,0)*
  • 3: (n+1,n)*| (m-n-1,0)
  • 4: (n+1,0) | (m-n-1,n)*
  • 5: (m,n)* | (0,n) (m-n-1 + n = m-1 ≤ k)
  • 사실 여기에 해당되는 (m,n)은 (3,1)이 유일하다
• m≤(n+1)*2인 경우에는 k=n+1로 잡고 7번만에 옮길수 있다.
  • 0: (0,0) | (m,n)*
  • 1: (0,n)*. | (m,0)
  • 2: (0,n) | (m,0)*
  • 3: (n+1,n)*| (m-n-1,0)
  • 4: (n+1,0) | (m-n-1,n)*
  • 5: (m,0)* | (0,n)
  • 6: (m,0) | (0,n)*
  • 7: (m,n)* | (0,0)
• 나머지 경우는 이제 처음 말했던 일반적인 방법을 따라야 한다. k=n+1로 잡고, 동쪽에 코너차가 n+1대 남을때까지 한대씩 서쪽으로 옮기는 과정을 반복해야 한다
  • 0: (0,0) | (m,n)*
  • 1: (0,n)*. | (m,0)
  • 2: (0,n) | (m,0)*
  • 3: (n+1,n)*| (m-n-1,0)
  • 4: (n+1,0) | (m-n-1,n)*
  • 5: (n+2,n)*| (m-n-2,0)
  • 6: (n+2,0) | (m-n-2,n)*
  • …
  • 2x+2: (n+x,0) | (m-n-x,n)* (m-n-x = n+1)
  • 2x+3: (m,0)* | (0,n)
  • 2x+4: (m,0) | (0,n)*
  • 2x+5: (m,n)* | (0,n)
  • 여기에서 (m-n-x == n+1) 이므로, x= m-2n-1 이다. 그러면 총 이동 횟수는 2m-4n+3
• 이렇게 지저분한 케이스워크를 처리해주면, O(1)에 테스트케이스 하나를 처리할 수 있다.

"""Solution code for "BOJ 31249. 주행시험장".

- Problem link: https://www.acmicpc.net/problem/31249
- Solution link: http://www.teferi.net/ps/problems/boj/31249

Tags: [ad hoc]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        n, m = [int(x) for x in sys.stdin.readline().split()]
        if n > m:
            n, m = m, n
        if m == n:
            print(n, 3)
        elif m <= n * 2:
            print(n, 7)
        elif m <= n + 2:
            print(n + 1, 5)
        elif m <= n * 2 + 2:
            print(n + 1, 7)
        else:
            print(n + 1, 2 * m - 4 * n + 3)


if __name__ == '__main__':
    main()