За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос "\textit{Кто последний?}", посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь. Однако, пока такие системы далеки от совершенства. Например, вызывает вопросы стандартный принцип любой очереди: "\textit{Первым обслуживается тот, кто первым пришел}". При разработке инновационной ГАС "Очередь" решено было сделать ее такой, что выполнение этого принципа не требуется. Вместо этого, новая система призвана минимизировать количество негатива, приходящегося на чиновника, на прием к которому стоят люди в очереди. Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен \textbf{w}, то через \textbf{t} часов ожидания в очереди этот человек обрушит на голову чиновника ровно \textbf{wt} единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого --- количество гнева будет равно \textbf{2w}. Также известно, что на обслуживание каждого посетителя уходит ровно час, а каждый посетитель приходит в начале какого-либо часа. Ваша задача заключается в том, чтобы по данным вам показателям раздражительности и временам прихода посетителей определить, сколько негатива достанется чиновнику при оптимальном порядке обслуживания клиентов. \InputFile В первой строке задано одно целое число \textbf{t} --- количество случаев, которые вам предстоит обработать. Далее следуют \textbf{t} описаний самих случаев. Описание каждого случая состоит из: числа \textbf{n} в первой строке --- количества посетителей, и \textbf{n} описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа \textbf{r_i} и \textbf{w_i} (\textbf{1} ≤ \textbf{r_i}, \textbf{w_i} ≤ \textbf{10^6}) --- номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно. Суммарное количество посетителей во всех случаях одного теста не превосходит \textbf{10^5}. \OutputFile Для каждого случая в отдельной строке выведите ответ --- минимальное суммарное количество негатива, которое получит чиновник.