Butt-head has n volumes of his favourite Encyclopedia For Stupid Teenagers. The volumes are numbered from 1 to n and arranged in a row. He doesn’t like strict order, but he dislikes complete chaos as well. Butt-head counts the distance of volumes’ pertmutation as the sum of differences between number and position for all volumes. In other words, if the permutation is (i_1, i_2, ... i_n), where i_k (1 ≤ k ≤ n) denotes the number of volume on k-th place, then its distance will be |i_1–1|+|i_2–2|+...+|i_n–n|. Butt-head has a favourite number d, and he wants to arrange the Encyclopedia volumes so, that the distance will be equal to d. In how many ways can he do this?
First line of input contains the quantity of tests T (1 ≤ T ≤ 100). Each of the next T lines contains data for one test: the quantity of volumes n (1 ≤ n ≤ 50) and the required distance d (0 ≤ d ≤ 10000), separated by a space. Numbers n, d are integer.
Output T lines of the form "Case #A: B", where A is the number of test (beginning from 1), B is the quantity of permutations of n volumes with distance d, taken modulo 100007.