Məsələlər
Замкнутое сокровище
Замкнутое сокровище
Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.
Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до $n$ ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.
По имеющимся значениям $n$ и $m$ определить такое наименьшее количество замков, что если ключи от них правильно распределить среди бандитов, то каждая группа состоящая из не менее чем $m$ бандитов сможет открыть все замки, но никакая группа из меньшего числа бандитов открыть все замки не сможет.
Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков --- ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.
\InputFile
Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n~(1 \le n \le 30)$ и $m~(1 \le m \le n)$.
\OutputFile
Для каждого теста вывести в отдельной строке минимальное количество необходимых замков.
Giriş verilənləri #1
4 3 2 5 1 10 7 5 3
Çıxış verilənləri #1
3 1 210 10