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 - một nhà toán học người Pháp. Tháp là một 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.

Input

• 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.

Giới hạn:

• ~1 ≤ T ≤ 300; 1 ≤ N ≤ 64; 3 ≤ M ≤ 64~.

Output

• 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.

Sample

Input #1

1
5 3

Output #1

31

Problem source: Chuyên Sơn La Online Judge