Gözətçi hər gecə zavoddakı müəyyən sayda otağı, hər otağın baş çəkilmə sırası və yoxlanması vaxtını müəyyənləşdirən qrafikə uyğun olaraq yoxlamalıdır. Hər gecə gözətçi öz işinə birinci otaqdan başlayır və sonuncu otağı yoxladıqdan sonra zavoddan çıxaraq evə gedir. Adətən, o bütün otaqları yoxlayır, lakin bizim əhvalatda bunu əslində etməyə də bilər. Gözətçinin yoxlama qrafikinə çıxış imkanı olan kolleqası ona sataşmaq və onu evinə gec getməyə məcbur etməklə bir gecə əylənmək istəyir. Bunun üçün o, gözətçi gələnə və işə başlayana qədər bəzi otaqlarda bəzi hoqqalar edə bilər. Hər hansı otaqdakı hər bir hoqqa gözətçini yanlış fikrə sala bilər ki, digər otaqda nə isə ola bilər. Mükəmməl hoqqa gözətçini otaqda yoxlamalı olduğu müddətdən daha artıq müddətdə qalmağa və yoxlamanı adi rejimdə yoxlamalı otaqda deyil, başqa bir otaqda davam etdirməyə məcbur edə bilər. Gözətçi yeni otağa daxil olarkən onu axıradək yoxlayır (beləliklə, o bütün otaqların hamısına baş çəkməyə də bilər). Məsələn, əgər beş otaq varsa və normal rejimdə onlar ardıcıl yoxlanılırsa, gözətçini 4-cü otağı yoxlamağa məcbur edən yeganə hoqqa \textbf{2}-ci otaqda baş veribsə, onda gözətçi \textbf{1 - 2 - 4 - 5 }yolunu keçəcək və evinə yollanacaq. Hoqqa otaqda yalnız o zaman effektli olur ki, gözətçi həmin otağa birinci dəfə daxil olur, əgər gözətçi bu otağa gələcəkdə baş çəkməli olacaqsa, o qeyri-effektli olacaq. Göstərilən məlumatlara malik olmaqla, Sizdən elə bir proqram yazmaq tələb olunur ki, kolleqaya gözətçinin zavodda qalma müddətini maksimal edən hoqqlar planını tərtib etməyə kömək etsin. \InputFile Birinci sətirdə testlərin \textbf{t }sayı yerləşir. Hər bir testin birinci sətrində otaqların \textbf{n (0 ≤ n ≤ 100)} sayı yerləşir. Sonrakı \textbf{n }sayda sətir otaqlara baş çəkmə qaydasını təsvir edir. Hər bir sətirdəki təsvirdə üç tam \textbf{d}, \textbf{td} və \textbf{tc} ədədləri yerləşir. Burada \textbf{d} -- gözətçinin otaqda adi rejimdə yoxlama zamanı qaldığı vaxt, \textbf{td} -- orada hoqqa baş verdikdə qaldığı müddət və \textbf{tc} isə hoqqa baş verdiyi halda gözətçinin getməli olduğu növbəti otağın nömrəsidir. İlk otağın nömrəsi həmişə \textbf{1}, sonuncunun nömrəsi isə \textbf{n-}dir. \textbf{Çıxış verilənləri }Çıxışa hər birində bir testin cavabı olan \textbf{t} sayda sətir verilir. Hər bir test üçün gözətçinin axırıncı yoxladığı otaqdan çıxa biləcəyi ən böyük vaxtı verməli.