Злети та падіння Короля#5128

Злети та падіння Короля

1 секунда

32 мегабайти

Складна

Король має охоронців різного зросту. Замість того, щоб вишикувати їх у порядку збільшення або зменшення зросту, він хоче розташувати їх так, щоб кожен охоронець був або нижчим, або вищим за своїх сусідів (тобто зріст змінювався вгору-вниз уздовж ряду). Наприклад, сім охоронців зі зростом $160$ , $162$ , $164$ , $166$ , $168$ , $170$ і $172$ см можуть бути розташовані як:

або, можливо:

Король хоче знати, скільки охоронців йому потрібно, щоб мати різний порядок вгору-вниз при кожній зміні варти на решту свого правління. Щоб це зробити, йому потрібно знати, для заданої кількості охоронців, $n$ , скільки існує різних порядків вгору-вниз:

Наприклад, якщо є чотири охоронці: $1$ , $2$ , $3$ , $4$ можуть бути розташовані як:

$1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423$ 1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423

Для цієї задачі ви напишете програму, яка приймає на вхід додатне ціле число $n$ , кількість охоронців, і повертає кількість порядків вгору-вниз для $n$ охоронців різного зросту.

Вхідні дані

Перший рядок вхідних даних містить одне ціле число $P$ , ( $1 \leq P \leq 1000$ 1 \leq P \leq 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних складається з одного рядка вхідних даних, що містить два цілі числа. Перше число, $D$ , є номером набору даних. Друге число, $n$ ( $1 \leq n \leq 20$ 1 \leq n \leq 20), є кількістю охоронців різного зросту.

Вихідні дані

Для кожного набору даних є один рядок вихідних даних. Він містить номер набору даних ( $D$ ), за яким слідує один пробіл, а потім кількість порядків вгору-вниз для $n$ охоронців.

Приклади

Приклад 1