코치

비티아니아 대학교 팀이 ACM ICPC 세계 결승 진출을 확정했다. 팀의 코치인 마틴과 마이클은 팀을 최대한 잘 준비시키려 한다. 이를 위해 앞으로 $n$일 동안의 훈련 일정을 세우려 한다. 어느 날에 훈련을 진행하려면 아침에 문제를 인쇄하고 웹 대회 시스템을 실행해야 하며, 오후에는 참가자들과 풀이를 논의해야 한다.

마틴과 마이클은 매일 대학교에 나온다. 마틴은 보통 매일 아침에 나오지만, 정확히 $a$일마다 지방정부 사무실에서 볼일을 봐야 해서 그런 날에는 오후에 대학교에 나온다. 마이클은 보통 매일 오후에 나오지만, $b$일마다 여자친구와 영화관에 가기 때문에 그런 날에는 아침에 나온다. 아침과 오후 모두 대학교에 코치가 없으면 훈련은 취소된다.

마틴은 다음 $a$일 중에서 처음으로 사무실에 갈 날을 고를 수 있다. 마찬가지로 마이클은 다음 $b$일 중에서 처음으로 여자친구와 영화관에 갈 날을 고를 수 있다. 두 사람이 일정을 최적으로 정할 때, 훈련을 진행할 수 있는 최대 날짜 수는 얼마인가?

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 100\,000$)가 주어진다. 다음 $t$개의 줄에는 각각 위에서 설명한 정수 $n$, $a$, $b$ ($1 \le n \le 10^{18}$, $1 \le a, b \le 10^9$)가 한 줄에 하나씩 주어진다.

각 테스트 케이스에 대해 훈련을 진행할 수 있는 날짜의 최대 수를 정수 하나로 출력한다.

첫 번째 예제에서 마틴과 마이클은 둘 다 2일에 처음으로 기본 일정에서 벗어난다. 그러면 처음 3일 동안 훈련이 진행된다.

두 번째 예제에서 마틴과 마이클은 각각 5일과 1일에 처음으로 기본 일정에서 벗어난다. 그러면 2, 4, 5, 6, 8, 10일에 훈련이 진행된다.