Пользователь Shlakoblock устроил среди зрителей его канала голосование, в какую игру он будет играть на следующем стриме. В голосовании представлены $$$n$$$ игр. Каждый зритель может проголосовать за любое подмножество этих игр, но за каждую игру можно проголосовать не более одного раза. В конце Shlakoblock выберет случайный голос и будет стримить игру, за которую этот голос был отдан.
Все, кроме вас, уже проголосовали — сейчас за $$$i$$$-ю игру проголосовали $$$v_i$$$ раз. Вы оцениваете удовольствие от стрима по $$$i$$$-й игре как $$$p_i$$$. За какие игры вам следует проголосовать, чтобы максимизировать математическое ожидание удовольствия от стрима?
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество тестов. Далее следуют описания тестов.
В первой строке каждого теста дано целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество игр.
В каждой из следующих $$$n$$$ строк этого теста даны два целых числа $$$p_i$$$ и $$$v_i$$$ ($$$0 \le p_i, v_i \le 1000$$$) — удовольствие от стрима по $$$i$$$-й игре и количество голосов, которое сейчас за нее отдано.
Гарантируется, что в каждом тесте хотя бы одно $$$v_i$$$ положительно.
Выведите $$$3t$$$ строк. Ответ на каждый тест должен состоять из трех строк.
В первой строке выведите несократимую рациональную дробь — максимально возможное математическое ожидание удовольствия от стрима.
Во второй строке выведите целое число $$$k$$$ ($$$0 \le k \le n$$$) — количество игр, за которые надо проголосовать.
В третьей строке выведите $$$k$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера игр, за которые надо проголосовать.
Если существует несколько возможных ответов, разрешается вывести любой из них.
2 5 10 5 4 7 6 3 8 2 2 4 4 1 1000 10 100 100 10 1000 1
6/1 2 1 4 2555/557 3 2 3 4
