Thi thử trước khi thi KV 2026

Lộc muốn rủ bạn bè sang nhà mình chơi một trò chơi mà ở đó mọi người ngồi vào một cái bàn tròn (trò này rất phổ biến mỗi dịp tết đến xuân về). Bàn tròn đó có \(n\) chỗ, và mỗi người cảm thấy thoải mái nhất khi nếu tổng số ghế trống bên trái và bên phải không ít hơn \(k\). Lộc muốn mời tối đa số bạn để mỗi người đều cảm thấy thoải mái.

Bạn hãy giúp Lộc xác định số người tối đa được mời.

Input

• Dòng đầu tiên chứa số \(T\) (\(1 \le T \le 1000\)) là số bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số tự nhiên \(n, k\).

Output

• Với mỗi test, đưa ra một số nguyên duy nhất là số người bạn tối đa có thể được mời.

Constraints

• \(3 \le n \le 10^{18}\)
• \(1 \le k \le n - 1\)

Example

1
6 1

4

Khang và Lộc đang chơi một trò chơi. Họ có \(n\) quả bóng được xếp thành một hàng và đánh số từ \(1\) đến \(n\). Ban đầu quả bóng có số hiệu \(i\) (\(i = 1, \dots, n\)) sẽ nằm ở vị trí thứ \(i\). Khang và Lộc sẽ lật ngược dãy các quả bóng liên tiếp nhau \(n\) lần, lần thứ \(i\) (\(i = 1, \dots, n\)) họ sẽ lật ngược các quả bóng từ vị trí \(i\) đến vị trí \(n\).

Ví dụ với \(n = 4\), quả bóng ban đầu được đặt là: 1 2 3 4

• Lần 1: 4 3 2 1
• Lần 2: 4 1 2 3
• Lần 3: 4 1 3 2
• Lần 4: 4 1 3 2

Yêu cầu: Hãy cho biết sau \(n\) lần lật ngược vị trí các quả bóng như trên thì ở vị trí thứ \(k\) là quả bóng mang số hiệu bao nhiêu?

Input

• Dòng 1: số nguyên dương \(T\) (\(1 \le T \le 1000\)) là số bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(n, k\).

Output

• Với mỗi bộ dữ liệu in ra một số nguyên cho biết ở vị trí thứ \(k\) là quả bóng mang số hiệu bao nhiêu sau \(n\) lần lật ngược dãy số.

Constraints

• \(1 \le k \le n \le 10^{15}\).

Example

2
5 4
6 1

2
6

Các nhà bác học tìm thấy một loại vi khuẩn mới khi lớp băng vĩnh cửu bị tan. Họ quyết định nhân giống để nghiên cứu. Đĩa chứa dung môi có hình chữ nhật và có thể coi là một lưới ô vuông kích thước vô hạn.

Ở thời điểm \(1\), vi khuẩn được cấy vào một ô. Cứ sau một đơn vị thời gian, vi khuẩn lại phát triển sang các ô bên cạnh:

• Ở thời điểm chẵn, vi khuẩn lan từ ô đã có sang ô kề cạnh chưa có vi khuẩn.
• Ở thời điểm lẻ, vi khuẩn lan sang ô kề cạnh và kề đỉnh chưa có vi khuẩn.

Hãy xác định số ô có vi khuẩn sau \(k\) đơn vị thời gian.

Input

• Gồm một dòng duy nhất chứa số tự nhiên \(k\) (\(1 \le k \le 10^9\)).

Output

• Đưa ra một số tự nhiên duy nhất là số ô có vi khuẩn sau \(k\) đơn vị thời gian.

Example

1

1

2

5

3

21

5

69

6

97

Cho một bảng hình vuông kích thước \(n \cdot n\). Hàng được đánh số từ \(1\) đến \(n\) theo hướng từ trên xuống, cột được đánh số từ \(1\) đến \(n\) theo hướng từ trái sang phải. Trên mỗi ô người ta gắn một bóng đèn. Như vậy có \(n^2\) bóng đèn được gắn trên bảng hình vuông. Ban đầu các bóng đèn đều tắt. Người ta lần lượt thực hiện hai chu kỳ nhấn công tắc bóng đèn như sau:

• Chu kỳ 1: Người ta nhấn \(n\) lần công tắc. Tại lần nhấn thứ \(i\) (\(1 \le i \le n\)), các bóng đèn ở hàng có chỉ số chia hết cho \(i\) đổi trạng thái (từ tắt thành sáng và ngược lại).
• Chu kỳ 2: Người ta nhấn \(n\) lần công tắc. Tại lần nhấn thứ \(i\) (\(1 \le i \le n\)), các bóng đèn ở cột có chỉ số chia hết cho \(i\) đổi trạng thái (từ tắt thành sáng và ngược lại).

Yêu cầu: Cho số nguyên dương \(n\). Hỏi sau cùng trên bảng hình vuông kích thước \(n \cdot n\) có bao nhiêu bóng đèn đang ở trạng thái sáng.

Input

• Một dòng duy nhất chứa số nguyên dương \(n\) (\(1 \le n \le 10^{10}\)).

Output

• In ra một số nguyên duy nhất là số lượng bóng đèn ở trạng thái sáng sau hai chu kỳ nhấn công tắc.

Example

2

2

3

4

6

16

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^7\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^{10}\).

Số chẵn lẻ đan xen là số nguyên dương mà hai chữ số liên tiếp trong số đó không cùng tính chẵn hoặc không cùng tính lẻ.

Ví dụ: 1236, 258, 123698, ... là các số chẵn lẻ đan xen.

Yêu cầu: Cho biết số chẵn lẻ đan xen thứ \(n\).

Input

• Một số nguyên dương \(n\).

Output

• In ra số chẵn lẻ đan xen thứ \(n\).

Constraints

• \(1 \le n \le 10^{15}\).

Example

1

1

100

290