불효자 찾기

은하는 평생 에메랄드를 모으는 데 힘썼고, 이제 이를 $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 \le T \le 500\,000)$

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

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