방탄 유리 시험 예산

사장은 자기 목숨이 위험하다고 여겨 차에 방탄 유리를 달았다. 그런데 이 유리가 정말 방탄인지 의심스럽다. $F$ 피트 떨어진 곳에서 한 발을 쐈더니 유리는 깨지지 않았지만, 더 가까이에서 쏘면 깨질지도 모른다.

유리에는 알려지지 않은 한계 거리 $D$가 있다. $D$ 피트 이상 떨어진 곳에서 쏜 총알은 유리를 깨뜨리지 못하고, $D$ 피트보다 가까운 곳에서 쏜 총알은 유리를 깨뜨린다. $F$ 피트에서 쏜 한 발이 유리를 깨뜨리지 못했으므로 $0 \le D \le F$이다. 사장이 알고 싶은 값이 바로 이 $D$이다.

시험은 정수 피트 위치에서만 한다. 총알 한 발을 쏘는 비용은 $B$이다. 쏜 총알에 유리가 깨지면 그 유리를 새로 마련하는 비용 $G$가 더 든다. 더 쏠 필요가 없어도 교체 비용은 똑같이 든다. 깨지지 않은 유리는 그대로 다음 한 발에 쓴다.

$F-1$ 피트에서 $0$ 피트까지 한 피트씩 내려가며 쏘면 깨지는 유리는 많아도 한 장이므로 $F \times B + G$ 이하의 비용으로 $D$를 알아낼 수 있다. 유리를 더 깨뜨리고 총알 수를 줄이는 쪽이 더 쌀 때도 있다.

어느 위치에서 깨지든 $D$를 반드시 알아낼 수 있어야 한다. 최악의 경우까지 감당하는 최소 예산을 구하라.

첫 줄에 시험 구성의 개수 $N$이 주어진다. ($1 \le N \le 100$)

다음 $N$개의 줄에 각각 세 정수 $F$, $G$, $B$가 공백으로 구분되어 주어진다. $F$는 유리가 깨지지 않는 것을 확인한 거리 ($1 \le F \le 1000$), $G$는 유리 한 장의 값 ($1 \le G \le 1000$), $B$는 총알 한 발의 값 ($1 \le B \le 100$)이다.

각 시험 구성마다 Case #n: 을 먼저 출력하고, 이어서 그 구성의 시험에 필요한 최소 예산을 출력한다. $n$은 입력에 주어진 순서대로 $1$부터 세는 구성 번호이다.