У Батхеда есть n томов его любимой Энциклопедии Для Глупых Подростков. Тома пронумерованы от 1 до n и выстроены в ряд. Он не любит строгого порядка, но также он не любит и полнейшего хаоса. Батхед рассчитывает дистанцию перестановки томов как сумму разностей номера и позиции для всех томов. Другими словами, если перестановка имеет вид (i1, i2, ... in), где ik (1 ≤ k ≤ n) означает номер тома на k-м месте, то её дистанция равна |i1 – 1| + |i2 – 2| + ... + |in – n|. Любимое число Батхеда равно d, и он хочет выстроить тома Энциклопедии так, чтобы дистанция была равна d. Сколькими способами он может это сделать?

Входные данные

Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 100). Каждая из следующих T строк содержит данные для одного теста: количество томов n (1 ≤ n ≤ 50) и требуемую дистанцию d (0 ≤ d ≤ 10000), которые разделены пробелом. Числа n, d – целые.

Выходные данные

Выведите T строк вида Case #A: B, где A – номер теста (начиная с 1), B – количество перестановок n томов с дистанцией d, взятое по модулю 100007.