eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Замкнутое сокровище

Замкнутое сокровище

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Группа из n бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее m из них.

Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до n ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.

По имеющимся значениям n и m определить такое наименьшее количество замков, что если ключи от них правильно распределить среди бандитов, то каждая группа состоящая из не менее чем m бандитов сможет открыть все замки, но никакая группа из меньшего числа бандитов открыть все замки не сможет.

Например, если n = 3 и m = 2, то достаточно 3 замков - ключи от замка 1 получают бандиты 1 и 2, ключи от замка 2 получают бандиты 1 и 3, ключи от замка 3 получают бандиты 2 и 3. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из 2 бандитов может открыть все замки. Можно убедиться, что 2 замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа n (1n30) и m (1mn).

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

Для каждого теста вывести в отдельной строке минимальное количество необходимых замков.

Пример

Входные данные #1
4
3 2
5 1
10 7
5 3
Выходные данные #1
3
1
210
10
Источник 2014 ACM North America - Rocky Mountain, Problem I