Bạn được cho một cây gồm N đỉnh (đánh số 1, 2, …, n) và một số nguyên k. Một cây con được định nghĩa là một đồ thị con liên thông trên cây. Nghĩa là, một cây con là một cây khác được tạo thành bằng các xóa một vài (có thể không xóa) đỉnh và tất cả các cạnh kề với những đỉnh đó. Một tập hợp con S các đỉnh được gọi là tốt nếu mọi cây con chứa tất cả các đỉnh trong S có ít nhất k đỉnh.

Yêu cầu: Hãy tìm kích thước nhỏ nhất của tập hợp con tốt?

Dữ liệu vào

Từ tập tin văn bản SUBTRCOV.INP có cấu trúc như sau:

• Dòng đầu tiên là một số nguyên T bộ test (1 ≤ T ≤ 100).
• Dòng tiếp theo chứa hai số nguyên n và k
• n – 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v thể hiện một cạnh nối hai đỉnh u và v của cây.

Dữ liệu ra

Ghi vào tập tin văn bản SUBTRCOV.OUT, Với mỗi test, in ra một dòng chứa kích thước của một tập hợp tốt.

Ràng buộc

• 1 ≤ n ≤ ~10^5~
• 1 ≤ k ≤ n
• 1 ≤ u, v ≤ n
• Các cạnh đã cho trong mỗi test tạo thành một cây.
• Tổng của n trong tất cả các test không vượt quá ~10^6~

Subtasks

• Subtask #1 (30 điểm): 1 ≤ n ≤ ~10^3~
• Subtask #2 (70 điểm): Các ràng buộc gốc.

Ví dụ

SUBTRCOV.INP:

2
7 5
1 2
2 3
3 4
3 5
5 6
3 7
6 4
1 2
1 3
1 4
1 5
1 6

SUBTRCOV.OUT:

2
3

Giải thích

• Test 1: Xem tập hợp S = {1, 6}. Cây con nhỏ nhất chứa cả hai đỉnh trong S là đường đi giữa chúng (1→2→3→5→6) chứa 5 đỉnh. Bởi k = 5, đáp án là 2.
• Test 2: Xem tập hợp S = {2, 3, 4}. Cây con nhỏ nhất chứa cả ba đỉnh trên sẽ chứa 4 đỉnh {1, 2, 3, 4}.

Hải rất giỏi toán học, Một ngày nọ, để kiểm tra lại trình độ toán học của anh ấy, Giáo viên đưa cho anh ấy một số nguyên N. Để gây ấn tượng với Thầy giáo, Hải phải chuyển N thành số nguyên M được biểu diễn dưới dạng: ~2^x~ + ~2^y~ (trong đó x và y là các số nguyên không âm sao cho x ≠ y). Để làm được điều đó, anh ấy cần thực hiện hai loại thao tác sau:

• Cộng 1 vào N
• Trừ 1 từ N

Yêu cầu: Hãy giúp anh ấy tìm ra số thao tác nhỏ nhất cần sử dụng để chuyển đổi N thành M hợp lệ?.

Dữ liệu vào

Từ tập tin văn bản NUMM.INP có cấu trúc như sau:

• Dòng đầu tiên là một số nguyên T bộ test (1 ≤ T ≤ 100).
• T dòng tiếp theo là số nguyên dương A duy nhất (1 ≤ A ≤ 100).

Dữ liệu ra

Ghi vào tập tin văn bản NUMM.OUT là với mỗi test, in ra một dòng duy nhất chứa một số nguyên – số các thao tác nhỏ nhất cần thực hiện

Ràng buộc

• 1 ≤ T ≤ ~10^5~
• 1 ≤ N ≤ ~10^9~

Subtasks

• Subtask #1 (30 điểm): 1 ≤ T ≤ 1000
• Subtask #2 (70 điểm): Ràng buộc gốc.

Ví dụ

NUMM.INP:

3
10
22
4

NUMM.OUT:

0
2
1

Giải thích

• Test 1: N = 10 thì nó đã có sẵn dạng ~2^x~ + ~2^y~ , với x = 3 và y = 1.
• Test 2: N = 22 cần được chuyển đổi thành M = 20 = ~2^2~ + ~2^4~ hoặc M = 24 = ~2^3~ + ~2^4~ trong 2 thao tác.
• Test 3: N = 4 cần được chuyển đổi thành M = 3 = ~2^0~ + ~2^1~ hoặc M = 5 = ~2^0~ + ~2^2~ trong 1thao tác.

Điện thoại của Sơn hiển thị thông báo Pin yếu nếu mức pin từ 15% trở xuống. Cho rằng mức pin của điện thoại Sơn là X%.

Yêu cầu: Hãy xác định xem điện thoại có hiển thị thông báo Pin yếu hay không.

Dữ liệu vào

Từ tập tin văn bản LOWBAT.INP có cấu trúc như sau:

• Dòng đầu tiên là một số nguyên T bộ test (1 ≤ T ≤ 100).
• T dòng tiếp theo là số nguyên dương A (1 ≤ A ≤ 100).

Dữ liệu ra

Ghi vào tập tin văn bản LOWBAT.OUT là với mỗi trường hợp thử nghiệm, xuất ra trên một dòng YES, nếu mức pin từ 15% trở xuống. Ngược lại, in NO

Subtasks

Subtask #1 (100 points)

Ví dụ

LOWBAT.INP:

3
15
3
65

LOWBAT.OUT:

YES
YES
NO