시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB148244329226.378%

문제

준겸이는 문자를 잘 안 본다. 어떻게 하면 준겸이가 문자를 보게 할 수 있을지 고민하던 중, 윤헌이는 같은 말을 정확히 $n$번 반복하면 반드시 준겸이가 문자를 확인한다는 사실을 알게 되었다.

그래서 윤헌이는 하고 싶은 말을 $n$번 반복하는 데 걸리는 시간이 궁금해졌다! 윤헌이는 하고 싶은 말을 타이핑해서 적거나, 지금까지 적은 문자를 복사/붙여넣기 할 수 있다.

지금까지 적은 문자를 복사/붙여넣기 하면 현재 적은 말의 개수가 정확하게 $2$배가 된다.

하고 싶은 말을 1번 적는 데 $s$초의 시간이 걸리고, 복사/붙여넣기 하는 데 $t$초의 시간이 걸린다고 할 때, 윤헌이가 하고 싶은 말을 정확히 $n$번 적는 데 걸리는 최소 시간을 출력하시오.

입력

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

각 테스트 케이스의 첫 줄에는 준겸이에게 보낼 같은 말의 개수 $n$이 주어진다.

각 테스트 케이스의 두번째 줄에는 하고 싶은 말을 적는 데 걸리는 시간 $s$와 복사/붙여넣기 하는 데 걸리는 시간 $t$가 공백으로 구분되어 주어진다.

출력

윤헌이가 하고 싶은 말을 정확히 $n$번 적는 데 걸리는 최소 시간을 출력한다.

제한

  • $1 \le T \le 10^4$
  • $1 \le n \le 10^{18}$
  • $1 \le s, t \le 10^9$

예제 입력 1

1
17
1 5

예제 출력 1

14