Ban tổ chức đã chuẩn bị rất nhiều kẹo cho các thí sinh, như là phần thưởng cho những nỗ lực không ngừng nghỉ của họ. Kẹo được ban tổ chức chia thành các gói để phân phát cho thí sinh. Số cái kẹo trong mỗi gói kẹo luôn luôn là số Fibonacci, và số lượng gói kẹo mỗi loại mà ban tổ chức có là vô hạn. Số Fibonacci được định nghĩa như sau:
- ~f_1 = 1~
- ~f_2 = 1~
- ~f_k = f_{k−1} + f_{k−2}~ ~∀k ≥ 3~
Giả sử có ~n~ thí sinh tham gia cuộc thi. Sau cuộc thi, các thí sinh sẽ được xếp hạng từ ~1~ đến ~n~ (không có hai thí sinh nào cùng hạng). Thí sinh hạng thứ i sẽ nhận được một số gói kẹo sao cho tổng lượng kẹo trong các gói đúng bằng ~n − i + 1~. Ban tổ chức đã chọn cách phát kẹo sao cho đối với mỗi thí sinh số gói kẹo nhận được là ít nhất. Có một vấn đề là việc chia kẹo rất tốn thời gian, vì thế những người nhận nhiều hơn hoặc bằng ~k~ gói kẹo sẽ được nhận kẹo của mình vào ngày hôm sau. Yêu cầu: Hãy tính tổng số gói kẹo của những người được nhận kẹo vào ngày hôm sau.
Dữ liệu vào
- Dòng đầu chứa số testcase: ~T~.
- ~T~ dòng tiếp theo mỗi dòng chứa hai số ~n, k~.
Kết quả
Gồm ~T~ dòng là kết quả cho ~T~ testcase theo thứ tự đầu vào.
Sample Input
3
6 2
4 2
5 1
Sample Output
4
2
6
Giải thích
Ở testcase ~3~, thí sinh hạng hai nhận ~2~ gói và bốn thí sinh còn lại mỗi người nhận ~1~ gói, tất cả đều nhận vào hôm sau.
Hạn chế
- ~1 ≤ T ≤ 10^5, 1 ≤ n, k ≤ 10^{15}~ trong tất cả các test
- 20% số test với ~n, k ≤ 10^5, T ≤ 100 ~
- 20% số test với ~n, k ≤ 10^5, T > 100 ~
- 30% số test với ~n > 10^5, T ≤ 100 ~
- 30% số test còn lại không có ràng buộc gì thêm
Nguồn: Trại đông Bảo Lộc 2021 - thầy Đỗ Phan Thuận
Comments