Злети та падіння Короля
Король має охоронців різного зросту. Замість того, щоб вишикувати їх у порядку збільшення або зменшення зросту, він хоче розташувати їх так, щоб кожен охоронець був або нижчим, або вищим за своїх сусідів (тобто зріст змінювався вгору-вниз уздовж ряду). Наприклад, сім охоронців зі зростом 160, 162, 164, 166, 168, 170 і 172 см можуть бути розташовані як:
або, можливо:
Король хоче знати, скільки охоронців йому потрібно, щоб мати різний порядок вгору-вниз при кожній зміні варти на решту свого правління. Щоб це зробити, йому потрібно знати, для заданої кількості охоронців, n, скільки існує різних порядків вгору-вниз:
Наприклад, якщо є чотири охоронці: 1, 2, 3, 4 можуть бути розташовані як:
1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
Для цієї задачі ви напишете програму, яка приймає на вхід додатне ціле число n, кількість охоронців, і повертає кількість порядків вгору-вниз для n охоронців різного зросту.
Вхідні дані
Перша строка вхідних даних містить одне ціле число P, (1 ≤ P ≤ 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних складається з одного рядка вхідних даних, що містить два цілі числа. Перше число, D, є номером набору даних. Друге число, n (1 ≤ n ≤ 20), є кількістю охоронців різного зросту.
Вихідні дані
Для кожного набору даних є один рядок вихідних даних. Він містить номер набору даних (D), за яким слідує один пробіл, а потім кількість порядків вгору-вниз для n охоронців.