Каждую ночь сторож должен проверить некоторое количество комнат на заводе в соответствии с графиком, который определяет порядок их посещения и время проверки каждой комнаты. Каждую ночь сторож начинает свою работу с первой комнаты, и уходит с завода домой, когда проверит последнюю. Обычно он проверяет все комнаты, но в нашей истории он может на самом деле этого не делать. Имея доступ к графику обхода, его коллега хочет повеселиться одну ночь, раздразнив сторожа и заставив того пойти домой очень поздно. Для этого он может сделать некоторые трюки в некоторых комнатах до того момента, как придет сторож и начнет свою работу. Каждый трюк в одной комнате вводит сторожа в заблуждение, как будто что-то может произойти в другой комнате. Совершенный трюк заставляет сторожа находиться другое количество времени в этой комнате и продолжить проверку в другой комнате, возможно не совпадающей с той, которую он должен проверять в обычном режиме. Когда сторож заходит в новую комнату, он продолжает проверять ее до конца (и таким образом может не посетить все комнаты). Например, если имеются пять комнат и они в нормальном режиме инспектируются последовательно, а единственный трюк совершается в комнате \textbf{2}, заставляющий сторожа направиться на проверку комнаты \textbf{4}, то в итоге сторож проделает путь \textbf{1 - 2 - 4 - 5} и уйдет домой. Трюк оказывается эффективным в комнате только когда сторож заходит в нее первый раз, и является неэффективным когда сторож посещает эту комнату в будущем. Имея указанную информацию, Вам следует написать программу, которая поможет коллеге составить план трюков, максимизирующий время пребывания сторожа на заводе. \InputFile Первая строка содержит количество тестов \textbf{t}. Первая строка каждого теста содержит количество комнат \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{100}). Следующие \textbf{n} строк описывают комнаты в порядке обхода. Каждая строка описания содержит три целых числа \textbf{d td tc}, где \textbf{d} - время которое сторож находится в комнате в случае обычной проверки, \textbf{td} - время нахождения в комнате, в случае если в ней совершается трюк, и \textbf{tc} - номер следующей комнаты, куда следует идти в случае совершения трюка. Начальная комната всегда имеет номер \textbf{1}, а конечная - номер \textbf{n}. \OutputFile Вывести \textbf{t} строк, каждая из которых содержит ответ на один тест. Для каждого теста вывести наибольшее время, через которое сторож сможет выйти из последней проинспектированной комнаты.