31249번 - 주행시험장

문제

현대모비스는 기술연구소(경기도 용인)에 400여 명의 연구원들이 소프트웨어 직무교육을 동시에 이수할 수 있는 소프트웨어 아카데미를 2018년부터 운영하고 있습니다. 현재 800여 명 수준인 국내 기술연구소의 소프트웨어 설계 인원을 2025년까지 약 4천 명으로 5배 이상 확충할 방침입니다.

국내 연구소의 소프트웨어 인력 육성, 확충과 더불어 인도연구소를 소프트웨어 전문 글로벌 연구 거점으로 확대하여 운영하고 있습니다.

또한 국내 부품업계 최초로 2018년 빅데이터팀을 신설하여 빅데이터와 인공지능을 연구개발에 적극 활용하고 있습니다.

현대모비스가 새롭게 건설한 주행시험장에서 두 종류의 인공지능 소프트웨어를 실차에 장착해 검증하고 있다. 각 소프트웨어는 전방 레이더와 코너 레이더에 연동되어 있다. 주행시험장에는 총 $n+m$대의 차가 있는데, 그중 전방 레이더가 장착된 차는 $n$대이고, 다른 $m$대에는 코너 레이더가 장착되어 있다.

이 주행시험장은 크게 동쪽과 서쪽 두 부분으로 나뉜다. 처음에 모든 차는 동쪽 주행시험장 안에서만 주행하고 있고, 당신도 동쪽 주행시험장에서 차들을 모니터링하고 있다. 당신은 당신이 있는 쪽의 주행시험장만 모니터링할 수 있고, 반대쪽 주행시험장은 모니터링할 수 없다.

아직 서로 다른 종류의 레이더끼리의 호환을 위한 기능을 아직 장착하지 않았기 때문에, 당신이 모니터링하지 않는 주행시험장에 서로 다른 종류의 레이더가 장착된 차량이 동시에 존재하면 차들이 주행 시험을 멈출 것이다. 당신의 목표는 차들이 주행 시험을 멈추지 않게 하면서 모든 차를 서쪽 주행시험장으로 이동시키는 것이다.

구체적으로, 동쪽 주행시험장과 서쪽 주행시험장을 잇는 길이 있다. 당신은 최소 0ドル$대, 최대 $k$대의 차를 동시에 끌고 한 주행시험장에서 다른 쪽 주행시험장으로 이동할 수 있다.

예를 들어 처음에 동쪽 주행시험장에 전방 레이더 3ドル$대와 코너 레이더 2ドル$대가 있고, $k=2$라고 하자. 그러면 당신은 코너 레이더가 장착된 차량 2ドル$대와 같이 길을 건너 서쪽 주행시험장으로 움직일 수 있다. 당신은 차를 끌고 움직인 후에 서쪽 주행시험장을 모니터링 할 수 있다. 마찬가지로, 당신은 다시 2ドル$대 이하의 차를 끌고 서쪽 주행시험장에서 동쪽 주행시험장으로 움직인 다음 동쪽 주행시험장을 모니터링할 수 있다.

주행 시험이 멈추는 일이 없이 차를 모두 서쪽 주행시험장으로 옮기기 위한 $k$의 최솟값을 구하고, 이때 당신이 길을 건너야 하는 최소 횟수를 출력하시오.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어진다.

다음 줄부터 각 테스트 케이스마다 $n$과 $m$의 값이 한 줄에 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 $k$의 최솟값과 그 때 길을 건너는 최소 횟수를 공백으로 구분하여 한 줄에 출력한다. 입력 범위 내에서 두 값은 모두 2ドル^{63}$보다 작음을 증명할 수 있다.

제한

• 1ドル\leq T\leq 100,円 000$
• 1ドル\leq n,m\leq 10^9$

힌트