Fegla와 빈대

mmaw라는 이름으로도 불리는 Fegla는 여러 팀을 지도한다. 모든 팀이 한 장소에서 함께 훈련하는데, 그곳은 환기가 잘 되지 않고 팀 수에 비해 상당히 좁다. 그러다 보니 이상한 생물이 나타났다. 바로 빈대다.

빈대는 기생충이라 사람을 물어 피를 빨아 먹는다. Fegla가 이상하게 여긴 점은 팀원 가운데 한 번도 물리지 않은 사람이 있다는 것이었다. 그래도 그의 관심은 빈대를 없애는 쪽에 있었다. 한동안 행동을 관찰한 끝에, 번식을 막아야 빈대를 없앨 수 있다는 결론을 내렸다. 빈대는 서로 아주 가까이 붙어야 번식한다.

그래서 Fegla에게는 도움이 필요하다. 빈 칸 $N$개가 일렬로 놓여 있고 빈대가 $K$마리 있다. 한 칸에는 빈대를 최대 한 마리까지 놓을 수 있다. 이웃한 두 빈대 사이에 있는 빈 칸의 개수를 모두 세었을 때 그 최솟값이 가장 커지도록 빈대를 배치해야 한다.

$N = 4$, $K = 2$일 때 가장 좋은 배치는 다음과 같고, 이웃한 두 빈대 사이의 빈 칸은 2개다.

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

다음 $T$개 줄에는 각 줄마다 정수 $N$과 $K$가 빈 칸을 사이에 두고 주어진다.

• $2 \le N \le 200$
• $2 \le K \le N$

각 테스트 케이스마다 한 줄에 답을 출력한다. 답은 가장 좋은 배치에서 이웃한 두 빈대 사이의 빈 칸 개수의 최솟값, 그중에서도 가능한 최댓값이다.