EGG Club Training

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