Бокс, каратэ, самбо… Классические боевые единоборства пресытили аудиторию. Поэтому известный спортивный канал запускает новый формат соревнований, основанный на традиционной русской забаве — боях стенка на стенку. В соревновании могут участвовать от двух до k команд, каждая из которых будет соперничать с остальными. Всего в соревновании примут участие n бойцов. Перед началом боя они должны разделиться на команды, каждый боец должен войти ровно в одну команду. За время боя два бойца сразятся, если они состоят в разных командах. Организаторы считают, что популярность соревнований будет тем выше, чем больше будет количество схваток между бойцами. Помогите распределить бойцов по командам так, чтобы максимизировать количество схваток между бойцами, и выведите это количество.
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В первой строке дано количество тестов T (1 ≤ T ≤ 10). В следующих T строках перечислены тесты. В каждой из них записаны целые числа n и k через пробел (2 ≤ k ≤ n ≤ 104).
Для каждого теста в отдельной строке выведите одно целое число — ответ на задачу.
| Исходные данные | Результат |
|---|---|
| 3 6 3 5 5 4 2 |
12 10 4 |