Đếm hoán vị theo số nghịch thế

Một hoán vị \(A = (a_1, a_2, \dots, a_n)\) của các số \(1, 2, \dots, n\) có một nghịch thế tại cặp chỉ số \((i, j)\) nếu \(i < j\) và \(a_i > a_j\).

Ví dụ, hoán vị \((2, 4, 1, 3)\) có đúng \(3\) nghịch thế: các cặp giá trị \((2,1)\), \((4,1)\) và \((4,3)\).

Cho hai số nguyên \(n\) và \(k\). Hãy đếm xem có bao nhiêu hoán vị của \(1, 2, \dots, n\) có đúng \(k\) nghịch thế.

Bài toán gồm nhiều bộ dữ liệu độc lập.

Input

• Dòng đầu tiên chứa số nguyên \(d\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu nằm trên một dòng gồm hai số nguyên \(n\) và \(k\), cách nhau một dấu cách.

Output

Với mỗi bộ dữ liệu, in ra trên một dòng số lượng hoán vị thoả mãn.

Constraints

• \(1 \le d \le 10\)
• \(1 \le n \le 12\)
• \(0 \le k \le 98\)

Sample Input

4
3 2
5 3
6 15
12 33

Sample Output

2
15
1
25598186

Explanation

Với \(n = 3\) và \(k = 2\), hai hoán vị có đúng \(2\) nghịch thế là \((2,3,1)\) và \((3,1,2)\). Với \(n = 6\) và \(k = 15\) chỉ có hoán vị đảo ngược hoàn toàn \((6,5,4,3,2,1)\).