주행시험장

현대모비스는 2018년부터 경기도 용인의 기술연구소에서 400여 명의 연구원이 소프트웨어 직무교육을 동시에 이수할 수 있는 소프트웨어 아카데미를 운영하고 있습니다. 국내 기술연구소의 소프트웨어 설계 인원은 현재 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$