초전도체 부수기

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

• $1 \le b < a$인 정수 $b$를 고른다.
• 이를 $b\mathrm{g}$짜리 조각 하나와 $(a-b)\mathrm{g}$짜리 조각 하나로 쪼갠다.
• 이 절단에는 $a$원의 비용이 든다.

연구 비용을 줄이기 위해, 초전도체를 $K$개의 조각으로 자르는 데 드는 최소 비용을 구해야 한다. 제한 조건 아래에서 위 방법으로 초전도체를 $K$개의 조각으로 쪼갤 수 있음은 증명할 수 있다.

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

이어지는 $T$개의 줄에는 각각 초전도체 덩어리의 무게 $N$과 샘플을 요청한 연구소의 수 $K$가 공백으로 구분되어 주어진다.

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

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