За останні декілька років електронні черги міцно увійшли у повсякденне життя. У багатьох державних установах можна зустріти термінал, який друкує папірець з номером, і, не задаючи звичне запитання "\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 Для кожного випадку у окремому рядку виведіть відповідь --- мінімальну сумарну кількість негативу, яку отримає чиновник.