Description

九皇后问题大家应该知道了吧，就是在9*9的棋盘上放9个皇后的方法总数,使每个皇后之间不能相互攻击到。如图所示，R1和R2能互相攻击，R1和R3不能攻击到，R3和R2也不能互相攻击。
 
                                                                    
 

 
现在，Zero想知道把k个皇后放到N*N的棋盘上有多少种方法，使皇后间不能互相攻击。
 
聪明的你帮帮Zero吧。

Input

开始输入组数T（T<=365）
 


 
 
然后后面每组输入两个数字 n (1 <=n <= 30) and k (0 <= k <= n^2).

Output

对于每组数据
 
输出Case x: sum
 
x为现在的组数，sum为发放总数

Sample Input

8
1 1
2 1
3 1
4 1
4 2
4 3
4 4
4 5

Sample Output

Case 1: 1
Case 2: 4
Case 3: 9
Case 4: 16
Case 5: 72
Case 6: 96
Case 7: 24
Case 8: 0

HINT

保证结果不超__int64

Source

Zero