THỰC HÀNH

Bài toán Tháp Hà Nội trở thành nổi tiếng vào năm 1883, sau bài báo của Luca là một nhà toán học người Pháp. Tháp là mỗi cọc đĩa đường kính giảm dần từ dưới lên trên . Bài toán đặt ra là cần chuyển chồng đĩa sang một cọc khác sử dụng một cọc trung gian sao cho trong quá trình chuyển đĩa không có đĩa nào có đường kính lớn hơn bị đặt lên trên đĩa có đường kính nhỏ hơn.

Yều cầu: Giải bài toán tháp Hà Nội tổng quát. Cho M cọc trong đó có một cọc là cọc xuất phát, một cọc là cọc đích, M – 2 cọc còn lại sử dụng làm cọc trung gian và tháp N đĩa, hãy xác định số lần chuyển đĩa tối thiểu cần thực hiện để chuyển chồng đĩa từ cọc xuất phát sang cọc đích sử dụng M-2 cọc còn lại như cọc trung gian.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương T là số bộ test.
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên N, M cách nhau bởi một dấu cách.

Dữ liệu ra:

Với mỗi cặp số nguyên N, M ở đầu vào, ghi ra trên một dòng đáp số tương ứng.

Ví dụ:

Dữ liệu vào:
1
5 3

Dữ liệu ra:
31

Giới hạn: 1 ≤ T ≤ 300; 1 ≤ N ≤ 64; 3 ≤ M ≤ 64;