Tụi trẻ con (xem bài EGG) thời nào nay đã lớn, nhưng vẫn tụ tập với nhau chơi trò thả trứng tìm lại tuổi thơ. Chúng tụ tập ở một tòa nhà có ~N~ tầng và trong tay có ~E~ quả trứng giống nhau. Biết rằng trứng nếu thả ở tầng ~1~ thì sẽ không vỡ, còn thả ở tầng thứ ~N~ thì chắc chắn sẽ vỡ. Khi thả trứng, nếu nó không vỡ thì sẽ nằm lại ở tầng ~1~, nên nếu muốn lấy lại chúng để thử tiếp thì phải đi cầu thang xuống tầng ~1~. Vì sức khỏe không còn như xưa, nên chúng phải hạn chế số tầng đi lên cầu thang. Cũng vì lí do này nên tòa nhà mà chúng tụ tập không có tới cả nghìn tầng nữa, mà sẽ chỉ có tối đa ~50~ tầng.

Yêu cầu: Hãy tìm ra số tầng phải leo lên ít nhất để xác định độ cứng của các quả trứng, biết rằng ban đầu chúng đứng ở tầng ~1~.

Input

Dòng ~1~: số test ~T~ ~\left(1 \leq T \leq 500\right)~

~T~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~N~ và ~E~ ~\left(2 \leq N \leq 50,\text{ } 1 \leq E \leq 10\right)~

Output

Với mỗi test in ra số tầng phải leo lên ít nhất trong trường hợp xấu nhất.

Sample Input

3
6 1
6 2
6 3

Sample Output

10
5
4