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

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

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

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

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

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

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

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

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

Примеры