마법의 약

민균이는 오늘도 어떻게 하면 귀여움을 받을 수 있을지 연구하느라 바쁘다. 그러다 신비의 나라에 가면 귀여움을 무한정 받을 수 있다는 이야기를 이웃 지호에게서 들었다. 지호는 힘들게 알아낸 방법을 그냥 알려 줄 수는 없다면서 민균이에게 다음 게임을 제안했다.

가방이 $N$개 있다. 그중 정확히 한 가방에만 신비의 나라로 보내 주는 마법의 약이 무한히 들어 있고, 나머지 가방에는 먹어도 아무 효과가 없는 약이 무한히 들어 있다. 가방은 서로 구분할 수 있지만, 가방에 든 약은 생김새가 모두 같아서 구분할 수 없다. 마법의 약을 먹은 사람은 그 즉시 신비의 나라로 간다.

민균이는 마법의 약이 어느 가방에 들어 있는지 알아내려고 실험을 한다. 실험을 시작하기 전에 원하는 수만큼 친구를 부르고, 실험은 여러 단계로 나누어 진행한다. 각 단계에서는 아직 신비의 나라로 가지 않은 친구 중 원하는 친구를 고른 다음, 원하는 가방의 약을 먹인다. 어떤 친구에게는 약을 하나도 먹이지 않을 수 있고, 어떤 친구에게는 여러 가방의 약을 먹일 수 있다. 마법의 약을 먹고 신비의 나라로 간 친구는 다음 단계부터 실험에 참여하지 못한다. 한 단계가 끝나면 민균이는 그 단계에서 사라진 친구가 누구인지를 알게 되고, 그 결과를 보고 다음 단계에서 누구에게 어떤 약을 먹일지 정할 수 있다.

예를 들어 가방이 10개이고 단계가 2번이라고 하자. 가장 단순한 방법은 친구를 10명 불러 각자 한 가방을 맡아 먹어 보게 하는 것이고, 이러면 한 단계 만에 답을 알 수 있다. 그런데 친구를 3명만 불러도 된다. 첫 단계에서 1, 2, 3번 가방의 약을 친구 1에게, 4, 5, 6번 가방의 약을 친구 2에게, 7, 8, 9번 가방의 약을 친구 3에게 먹인다. 아무도 사라지지 않으면 10번 가방이 답이다. 친구 1이 사라졌다면 답은 1, 2, 3번 가방 중 하나이므로, 두 번째 단계에서 1번 가방의 약을 친구 2에게, 2번 가방의 약을 친구 3에게 먹인다. 친구 2가 사라지면 1번, 친구 3이 사라지면 2번, 아무도 사라지지 않으면 3번 가방이 답이다. 반면 친구가 2명뿐이면 어떤 방법을 써도 두 단계 안에 답을 알아낼 수 없다.

가방의 개수 $N$과 실험 단계 수 $E$가 주어질 때, 마법의 약이 든 가방을 $E$단계 안에 항상 알아낼 수 있는 가장 적은 친구 수 $F$를 구하라. 최솟값이 아닌 값을 답하면 지호가 게임을 즉시 중단하므로 정확히 최솟값을 구해야 한다.

첫 줄에 질의의 개수 $T$ ($1 \le T \le 100$)가 주어진다. 이어지는 $T$개의 줄에 각각 $N$ ($1 \le N \le 10^6$)과 $E$ ($1 \le E \le 10$)가 공백으로 구분되어 주어진다.

각 질의마다 최소 친구 수 $F$를 한 줄에 하나씩 출력한다.