Замкнутое сокровище
Замкнутое сокровище
Группа из n бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее m из них.
Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до n ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.
По имеющимся значениям n и m определить такое наименьшее количество замков, что если ключи от них правильно распределить среди бандитов, то каждая группа состоящая из не менее чем m бандитов сможет открыть все замки, но никакая группа из меньшего числа бандитов открыть все замки не сможет.
Например, если n = 3 и m = 2, то достаточно 3 замков - ключи от замка 1 получают бандиты 1 и 2, ключи от замка 2 получают бандиты 1 и 3, ключи от замка 3 получают бандиты 2 и 3. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из 2 бандитов может открыть все замки. Можно убедиться, что 2 замков для этого случая не достаточно.
Входные данные
Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа n (1 ≤ n ≤ 30) и m (1 ≤ m ≤ n).
Выходные данные
Для каждого теста вывести в отдельной строке минимальное количество необходимых замков.
Пример
4 3 2 5 1 10 7 5 3
3 1 210 10