Замкнений скарб

Група з $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)$.

Вихідні дані

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

Приклади