23323번 - 황소 다마고치

문제

홍익대학교 캐릭터 '황소' - 출처 : 홍익대학교 홈페이지

홍익대학교를 대표하는 캐릭터 "황소"는 귀여운 모습으로 모든 홍익대학교 학생들의 사랑을 받고 있다. 학교에서는 이런 학생들의 수요 때문에 다양한 황소 굿즈 상품들을 내고 있는데, 이번에 새로운 상품으로 황소 다마고치가 출시되었다!

황소 다마고치는 작은 기계 안에서 황소를 애완동물로 키울 수 있는 장난감이다. 황소에게는 "체력" 수치가 존재하기 때문에, 잊지 말고 꼬박꼬박 먹이를 줘야 한다.

• 매일 낮에, 황소에게 원하는 만큼 먹이를 줘 그만큼 체력을 올릴 수 있다. 즉, (0ドル \le x \le$ 현재 가지고 있는 먹이의 개수)를 만족하는 정수 $x$를 고른다. 가지고 있는 먹이의 수가 $x$만큼 감소하고, 황소의 체력이 $x$만큼 증가한다.
• 매일 밤에, 황소의 체력이 절반으로 줄어든다 (나눈 후 소수점 이하는 버린다). 만약 체력이 0ドル$이 되었다면, 황소는 죽고 만다.

문제는 가지고 있는 먹이는 한정되어 있다는 것이다. 과연 현재 가진 먹이로 황소가 최대 며칠째까지 생존 가능할까?

입력

첫 번째 줄에 테스트 케이스의 개수 $T$ (1ドル \le T \le 1000$)가 주어진다.

다음 $T$개의 줄에 걸쳐서, 황소의 초기 체력을 나타내는 정수 $n$과, 현재 가지고 있는 먹이의 개수 $m$이 주어진다. (1ドル \le n,m \le 10^{12}$)

출력

$T$개의 줄에 걸쳐 주어진 순서대로, 황소를 가장 오래 살릴 수 있는 방법으로 먹이를 주었을 때 며칠째 밤에 죽게 되는지 출력한다.

입력, 출력의 값이 32비트형 정수(C/C++의 int)의 최댓값을 넘을 수 있음에 주의하자.

제한

힌트