불효자 찾기

은하는 평생 에메랄드를 모으는 데 힘썼고 이제 이것을 $N$명의 자식들에게 물려줄 때가 되었습니다. 은하는 가지고 있는 에메랄드를 $N$명의 자식들에게 각각 $K$개씩 나누어주고, 꼭 필요할 때 사용하라고 신신당부했습니다. 애프터눈 티타임을 즐기고 있던 어느 날, 자식 중 정확히 한 명이 에메랄드를 모두 팔아 버렸다는 사실이 은하의 귀에 들어가게 되었습니다.

은하는 에메랄드를 모두 팔아버린 불효자가 누군지 찾기 위해 자식들에게 준 에메랄드를 다음과 같은 방법으로 돌려달라고 했습니다.

• 에메랄드를 돌려받을 일수 $X$와 $i$번째 날에 $j$번째 자식에게서 돌려받을 에메랄드의 수 $\{a_{ij}\}$를 정합니다. 단, $a_{ij}$는 음이 아닌 정수이고, $j$번째 자식이 내야 하는 에메랄드 총수 $\sum_{i=1}^{X}a_{ij}$는 $K$ 이하여야 합니다. $(1\le i\le X;$ $1\le j\le N)$

• $i=1,\cdots ,X$에 대해 다음을 반복합니다.

  1. $i$번째 날 오전, $j$번째 자식이 에메랄드 $a_{ij}$개를 금고에 담습니다. 단, $j$번째 자식이 에메랄드를 모두 팔아버렸다면 에메랄드를 금고에 담을 수 없으므로 아무것도 하지 않습니다.
  2. $i$번째 날 오후, 은하는 금고에 에메랄드가 총 몇 개 있는지 확인하고, 모든 에메랄드를 가져갑니다.

은하는 적절한 $X$와 $\{a_{ij}\}$를 정하면 불효자를 찾을 수 있다는 것을 깨달았습니다.

이 방법의 큰 문제는 $X$일이라는 긴 시간이 걸린다는 것입니다. 아니나 다를까, 자식들은 다른 일로 바쁘다며 $X$를 최대한 줄여 달라고 요청했습니다. 여러분은 은하를 도와 $N$과 $K$가 주어지면 불효자를 한 명으로 특정할 수 있는 최소의 $X$를 찾아야 합니다.

첫 줄에 테스트케이스의 수 $T$가 주어집니다. $(1\leq T\leq 500\,000)$

각 테스트케이스의 첫 줄에 자식의 수 $N$과 자식 각자에게 준 에메랄드의 수 $K$가 공백으로 구분되어 주어집니다. $(2 \leq N \leq 10^{18};$ $1 \leq K \leq 10^{18})$

각 테스트케이스에 대해 한 줄에 하나씩 불효자를 특정할 수 있는 최소의 날수 $X$를 출력해야 합니다.