아이스크림 고르기

슈퍼마켓 냉동고 앞에 서서 저녁 식사 후에 먹을 아이스크림을 $n$가지 중에서 하나 골라야 한다. 한참 들여다봤지만 전부 맛있어 보여서 결정을 포기했다. 대신 주머니에 있던 공정한 $k$면 주사위를 꺼내 운에 맡기기로 한다.

종류의 수 $n$이 $k$와 같다는 보장이 없으니, 주사위를 한 번 굴려 나온 값 $i$로 $i$번째 종류를 고르는 방법을 항상 쓸 수는 없다. 그래서 주사위를 0번 이상 굴려서 모든 종류가 정확히 같은 확률로 뽑히도록 하는 알고리즘이 필요하다. 기각 표본 추출법(accept-reject method)을 쓰면 이렇게 공정하게 고를 수 있다.

그러다 같은 날 오후에 절대 늦으면 안 되는 대회가 있다는 사실이 떠올랐다. 기각 표본 추출법은 공정한 결과가 나오기까지 굴려야 하는 횟수에 상한이 없어서, 냉동고 앞에 오래 서 있다가 대회를 놓칠 수도 있다. 그러니 공정하면서 최악의 경우에 굴리는 횟수가 가장 적은 알고리즘을 찾기로 한다.

$n$과 $k$가 주어질 때, 한 번 실행에 주사위를 최대 $i$번만 굴리는 공정한 알고리즘이 존재하는 가장 작은 $i$를 구하라.

첫째 줄에 테스트 케이스의 개수를 나타내는 양의 정수 하나가 주어진다. 이 값은 100 이하다.

이어서 각 테스트 케이스마다:

• 한 줄에 공백으로 구분된 정수 $n$과 $k$가 주어진다 ($1 \le n, k \le 10^9$). $n$은 아이스크림 종류의 수, $k$는 주사위 면의 수다.

각 테스트 케이스마다:

• 공정한 선택이 반드시 가능해지는 최소 굴림 횟수를 정수 하나로 한 줄에 출력한다. 그런 횟수가 없으면 대신 unbounded를 출력한다.

$n = 4$, $k = 20$이면 한 번만 굴려도 충분하다.