Взлеты и падения Короля
Король имеет охранников разного роста. Вместо того чтобы выстроить их в порядке увеличения или уменьшения роста, он хочет расположить их так, чтобы каждый охранник был либо ниже, либо выше своих соседей (то есть, чтобы росты чередовались вверх и вниз вдоль ряда). Например, семь охранников с ростом 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 охранников.