Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT134H - Sắp xếp xen kẽ

Bố của Tí là một nghệ nhân đồ mỹ nghệ. Công việc chính của ông là làm các pho tượng bằng gỗ. Tí rất thích thú với những sản phẩm của bố mình. Cậu thường bảo bố đồ chơi cho mình.

Tí sắp xếp các tượng gỗ của mình theo 1 hàng, và cậu thích sắp xếp xen kẽ theo chiều cao, tức là một tượng gỗ có chiều cao cùng nhỏ hơn hoặc cùng lớn hơn cái đằng trước và cái đằng sau.

Ví dụ Tí có 7 bức tượng có chiều cao lần lượt là 160, 162, 164, 166, 168, 170 và 172 mm . Tí có thể sắp xếp như sau:

hoặc

Và Tí muốn biết mình có tất cả bao nhiêu cách sắp xếp, biết rằng chiều cao của các tượng gỗ là phân biệt.

Cụ thể, Tí có n tượng gỗ và có chiều cao được sắp xếp sẵn theo số thứ tự là 1, 2, ..., n. Các bạn hãy giúp Tí giải quyết bài toán này.

Ví dụ, với n = 4, thứ tự các bức tượng lần lượt là 1, 2, 3, 4, sẽ có tất cả 10 cách sắp xếp, đó là:

1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423

Input

Dòng đầu tiên là số bộ test (<= 1000).

Mỗi dòng tiếp theo gồm 2 số, số thứ tự của bộ test và số n là tượng gỗ mà Tí hiện có (n <= 20).

Output

Với mỗi test, in ra trên 1 dòng 2 số, số thứ tự của bộ test và đáp án trong trường hợp đó.

Example

Input:
4 
1 1 
2 3 
3 4 
4 20
Output:
1 1
2 4 
3 10 
4 740742376475050

Được gửi lên bởi:adm
Ngày:2013-02-28
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14 JAVA PAS-FPC PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.