Топский хочет построить сеть по доставке информации. Сеть содержит исходный сервер и несколько зеркальных серверов как показано на рисунке. Входные данные находятся в начальном сервере (в корне на рисунке \textbf{1}), в то время как их копии доставляются в некоторые зеркальные сервера (вершины \textbf{2} и \textbf{5} на рисунке \textbf{1}). Когда узел посылает запрос на поиск данных, то он старается найти их местоположение следующим образом. \begin{enumerate} \item Проверяем, находится ли копия данных в узле. Если да, то запрос выполнен. Иначе переходим на шаг \textbf{2}. \item Передаем запрос родителю, который совершает шаг \textbf{1}. \end{enumerate} \includegraphics{https://static.e-olymp.com/content/74/74dc1d0e865c9bc90e76b6fa575090a3ee7fcb83.jpg} Стоимость выполнения запроса \textbf{C}(\textbf{v}) определяется как сумма весов ребер на пути. Если \textbf{C}(\textbf{v}) не больше верхней границы \textbf{Q}(\textbf{v}), то стоимость поиска считается приемлемой. Топский предполагает также существование неотрицательной стоимости \textbf{S}(\textbf{v}) записи данных в вершине \textbf{v}. Исходный сервер специальный, стоимость сохранения данных в нем равна \textbf{0}. Топский хочет расположить на серверах копии данных таким образом, чтобы стоимость поиска для всех вершин была приемлемой, а суммарная стоимость записи данных была бы наименьшей. \InputFile Первая строка содержит количество тестов \textbf{t} (\textbf{t} ≤ \textbf{20}). Каждый тест начинается целым числом \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{1000}), которое указывает на количество серверов. Далее идут \textbf{n} строк, каждая из которых содержит четыре целых числа \textbf{F_v} (\textbf{0} ≤ \textbf{F_v} ≤ \textbf{n}), \textbf{Q_v}, \textbf{S_v} и \textbf{W_v} (\textbf{0} ≤ \textbf{Q_v}, \textbf{S_v}, \textbf{W_v} ≤ \textbf{10^5}). В строке \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}), \textbf{F_v} обозначает отца вершины \textbf{i} (если \textbf{F_v} равно \textbf{0}, то \textbf{i} является исходным сервером, \textbf{Q_v} равно \textbf{-1}, \textbf{S_v} равно \textbf{0} и \textbf{W_v} равно \textbf{0}), \textbf{Q_v} является верхней границей стоимости поиска, \textbf{S_v} равно стоимости записи данных в вершине \textbf{i}, а \textbf{W_v} равно весу ребра, соединяющего вершины \textbf{i} и \textbf{F_v}. \OutputFile Для каждого теста в отдельной строке вывести минимальную стоимость затрат на хранение данных.