Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HSPC14D - Đội mũ

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],..., 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],..., a[k], next(a[1]), next(a[2]),..., 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)

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],..., 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],..., a[k], next(a[1]),
next(a[2]),..., 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 ≤ Q ≤ 310000). Q dòng tiếp, mỗi dòng là một cặp số p, n (1 ≤ n ≤ 10^18 , 2 ≤ p ≤ 10^18 ).

Output

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

Example

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

Output:
0
1
1
2
1
2
2
3
1
2

Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-07-27
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSPC 2014

hide comments
2017-06-23 21:58:50
gao_đỏ :))
2014-07-30 18:54:04 Lương Ðức Tuấn Ðạt


Last edit: 2014-07-30 18:57:06
2014-07-28 03:22:42 Lollipop
input la nhap n p
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.