Từ xưa đến nay, việc phân chia học sinh vào từng khoa của trường Hogwart được thực hiện bởi những chiếc mũ phép thuật. Trước kia, trường có ~4~ khoa. Tuy nhiên, sau khi tái cơ cấu lại trường, số khoa thay đổi thành ~p~. Những chiếc mũ vẫn được sử dụng để phân chia học sinh.

Kế hoạch phân chia học sinh vào từng khoa được biểu diễn bằng dãy số ~a_{1}, a_{2}, \dots, a_{k}~, trong đó ~a_i~ là khoa mà học sinh ~i~ sẽ học. Cách phân chia học sinh của chiếc mũ được mô tả như sau: Các khoa trong trường được đánh số từ ~0~ đến ~p - 1~. Gọi ~next(x)~ là khoa kế tiếp của khoa ~x~ với ~next(x)~ ~= x + 1~ với ~x < p - 1~ và ~next(p - 1)~ ~= 0~. Kế hoạch phân chia được bắt đầu bằng một dãy số có duy nhất ~1~ phần tử ~0~. Sau mỗi bước, dãy ~a~ với ~k~ phần tử sẽ trở thành dãy số mới có ~2k~ phần từ ~a_{1}, a_{2}, \dots, a_{k}, next( a_{1} )$$, next( a_{2} ), \dots, next( a_{k} )~.

Xét ví dụ về việc phân chia ~9~ học sinh vào ~4~ khoa. Chiếc mũ sẽ thực hiện theo kế hoạch: ~(0)~, ~(0~, ~1)~, ~(0~, ~1~, ~1~, ~2)~, ~(0~, ~1~, ~1~, ~2~, ~1~, ~2~, ~2~, ~3)~, ~(0~, ~1~, ~1~, ~2~, ~1~, ~2~, ~2~, ~3~, ~1~, ~2~, ~2~, ~3~, ~2~, ~3~, ~3~, ~0)~, ...Độ dài của dãy cuối đủ cho ~9~ học sinh.

Cho các cặp số ~p~, ~n~. Nhiệm vụ của bạn là cho biết khoa nào trong số ~p~ khoa của trường mà học sinh thứ ~n~ sẽ vào học ở đó (học sinh được đánh số từ ~1)~.

Input

Dòng đầu là số truy vấn ~Q~ ~(1 \leq Q \leq 310000)~. ~Q~ dòng tiếp, mỗi dòng là một cặp số ~p~, ~n~ ~(1 \leq n \leq 10^{18}~, ~2 \leq p \leq 10^{18})~.

Output

In ra ~Q~ dòng lần lượt là đáp án của ~Q~ truy vấn

Sample Input

10
1 4
2 4
3 4
4 4
5 4
6 4
7 4
8 4
9 4
10 4

Sample Output

0
1
1
2
1
2
2
3
1
2