전기공

마을 J에는 인터넷이 연결된 집이 $n$채 있다. 그중 한 집에는 악성 사용자가 살면서, 가짜 계정으로 우리를 비난하는 댓글을 소셜 미디어에 계속 올리고 있다. 우리는 그 집이 어디인지 모르며, 이를 알아내고 싶다.

변전소에는 집마다 스위치가 하나씩, 모두 $n$개 있다. 스위치가 켜져 있으면 해당 집에 불이 들어와 있고, 꺼져 있으면 불이 없으며 인터넷도 끊긴다. 처음에는 모든 스위치가 켜져 있다. 매 시간이 시작될 때 스위치 상태를 원하는 대로 바꿀 수 있다. 일부는 켜고 일부는 끌 수 있다. 그 뒤 다음 한 시간 동안 소셜 미디어를 관찰한다. 악성 사용자의 집에 불이 있으면 댓글이 반드시 달리고, 불이 없으면 댓글이 달리지 않는다. 조사가 끝나면 모든 집의 불을 다시 켜서 원래 상태로 되돌려야 한다.

악성 사용자의 집 불이 $k$번보다 많이 꺼지면 그 사용자가 의심을 품게 되므로 이는 피하고 싶다. 불이 오래 꺼져 있는 것은 괜찮고, 세는 것은 불을 끈 횟수다. 악성 사용자가 사는 집을 확실히 알아내고 모든 집의 불을 복구하는 데 필요한 최소 시간은 몇 시간인가?

첫 줄에는 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 2 \cdot 10^5$). 이어서 각 줄에 정수 $n$과 $k$가 주어지는 테스트 케이스가 $t$개 있다. $n$은 집의 수이고, $k$는 악성 사용자의 집 불을 끌 수 있는 최대 횟수이다 ($1 \leq n, k \leq 10^{18}$).

각 테스트 케이스마다 한 줄에 정답을 출력한다. 정답은 악성 사용자의 집을 알아내고 모든 집의 불을 복구하는 데 필요한 최소 시간이다.

첫 번째 테스트 케이스는 $n = 3$, $k = 1$이다. 첫 시간에는 1번과 2번 집의 불을 끈다. 한 시간 뒤 1번 집의 불을 다시 켜고, 또 한 시간 뒤 2번 집의 불을 다시 켠다. 세 번째 시간이 시작될 때 악성 사용자가 사는 집을 확실히 알게 되며, 이때 모든 집의 불을 복구한다.