Cəhənnəmdən gələn kolleqa#5042
Hər gecə gözətçi zavodda müəyyən sayda otağı, hər otağın baş çəkilmə sırası və yoxlanma vaxtını müəyyən edən qrafikə uyğun olaraq yoxlamalıdır. Hər gecə gözətçi işinə birinci otaqdan başlayır və sonuncu otağı yoxladıqdan sonra zavoddan çıxır və evə gedir. Adətən o, bütün otaqları yoxlayır, lakin bu məsələdə bunların hamısını etməyə bilər.
Gözətçinin yoxlama qrafikinə sahib kolleqası onu incitmək və gec evə getməsi üçün bir gecə zarafat etmək istəyir. Bunun üçün o, gözətçi gəlməmişdən və işə başlamamışdan əvvəl bəzi otaqlarda tələ qurur. Hər bir otaqdakı tələ gözətçini aldadıb, sanki başqa otaqda nəsə baş verir. Bu halda, gözətçi həmin otaqda fərqli vaxt keçirir və yoxlamanı başqa otaqda davam etdirir, hansı ki bu otaq normaldan fərqli ola bilər. Yeni otağa keçdikdə isə yoxlama normal qaydada davam edir və nəticədə bəzi otaqlar yoxlanmaya bilər. Məsələn, əgər beş otaq var və yalnız ikinci otaqda tələ quraşdırılıbsa və bu tələ sayəsində gözətçi dördüncü otağa yönləndirilirsə, onda onun yolu belə olacaq: 1 - 2 - 4 - 5, və sonradan evə gedəcək. Tələ hər bir otağa yalnız ilk gəlişində təsir edir və növbəti gəlişlərdə təsirsizdir. Verilmiş məlumatlardan istifadə edərək, kolleqaya elə bir plan qurmağa kömək edən proqram tərtib etməlisiniz ki, gözətçi zavodda mümkün qədər çox vaxt keçirsin.
Birinci sətirdə — testlərin sayı verilir. Hər bir testin ilk sətirində bir ədəd (0 \leq n \leq 100) — otaqların sayı verilir. Daha sonra sətir boyunca otaqlar haqqında məlumat verilir. Hər bir sətir üç tam ədəd — ehtiva edir, burada — adi yoxlama zamanı otaqda keçirdiyi vaxt, — tələ qurulduqda orada qaldığı müddət, — tələ baş verəndə keçid edəcəyi növbəti otaqdır. Başlanğıc otaq həmişə , sonuncu isə həmişə -ci olur.
Çıxışda hər test üçün bir cavab olmaqla sətir verilir. Hər bir test üçün gözətçi sonuncu yoxladığı otaqdan çıxa biləcəyi ən böyük vaxtı çap edin.
Nümunə
1
5
2 99 4
2 2 3
2 2 4
2 2 5
2 2 5105Nümunə 1