초전도체 부수기

당신은 상온 상압 초전도체를 개발하고 세상을 뒤바꿀 논문을 작성했다. 당신은 $N\mathrm{g}$의 초전도체 덩어리를 가지고 있는데, 논문 검증을 위해 $K$개의 연구소에서 초전도체 샘플을 요청했다! 각 연구소에는 $1\mathrm{g}$ 이상의 초전도체 샘플을 보내주면 된다. 다행히도, 당신은 초전도체를 정밀하게 부수는 기술을 가지고 있다. $2$ 이상의 정수 $a$에 대하여, $a\mathrm{g}$의 초전도체를 다음과 같은 방법으로 절단할 수 있다.

• $1$ 이상 $a$ 미만의 정수 $b$를 선택한다.
• $b\mathrm{g}$ 짜리 초전도체와 $(a-b)\mathrm{g}$짜리 초전도체 두 개로 쪼갠다.
• 이때, $a$원의 비용이 든다.

연구 비용 절감을 위해 초전도체를 $K$개의 조각으로 자르기 위한 최소 비용은 얼마일지 구해야 한다. 단, 제한 조건하에서 위의 방법을 통해 초전도체를 $K$개의 조각으로 쪼갤 수 있음을 증명할 수 있다.

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

$T$ 개의 줄에 이어, 각 테스트 케이스마다 한 줄에 초전도체 덩어리의 무게 $N$과 초전도체 샘플을 요청한 연구소의 수 $K$가 공백을 사이에 두고 주어진다.

각 테스트 케이스마다 초전도체를 $K$개의 조각으로 자르기 위한 최소 비용을 출력한다.

• $1 \leq T \leq 100\,000$
• $2 \leq K \leq N \leq 1\,000\,000\,000$
• 주어지는 모든 수는 정수이다.