F. Модны тухай хялбар бодлого

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бат, Цэцэг хоёр хоёртын модоор тоглож байлаа. Хоёртын модны орой нэг бол навч, нэг бол хоёр хүүхэдтэй. Мөн навч бүр дээр тоо бий.

Тоглогч өөрийн ээлжин дээрээ дурын ижил эцэгтэй хоёр навч сонгон арилган, харгалзах тоонуудын аль нэгийг эцэгт нь шилжүүлнэ. Хэрэв цор ганц орой үлдвэл тоглоом дуусна.

Бат тоглоомыг эхлүүлэх ба түүний зорилго нь эцсийн орой дээр үлдэх тоог хамгийн их байлгах юм. Цэцэг харин хамгийн бага байлгахыг хүснэ. Хоёр тоглогч зөв тогловол хамгийн сүүлд ямар тоо үлдэх вэ?

Оролт

Эхний мөрөнд тестийн тоог илэрхийлэх $t$ ($1 ≤ t ≤ 100$) гэсэн бүхэл тоо байна. Дараа нь $t$ тест өгөгдөнө. Тест бүр хоосон мөрөөр эхлэх ба дараагийн мөрөнд $n$ ($1 ≤ n ≤ 250$) гэсэн бүхэл тоо байна. Дараагийн $n$ мөрөнд оройнуудыг тайлбарлана. Тэдгээр $n$ мөр бүрт нэг бол навчийг илэрхийлэх түүнд харгалзах сөрөг биш $a_{i}$ ($0 ≤ a_{i} ≤ 1000$) тоо байна, эсвэл навч биш болохыг илэрхийлэх $ - 1$ гэсэн тоо байх ба араас нь түүний хоёр хүүхдийг илэрхийлэх $l$ ба $r$ ($0 ≤ l, r ≤ n - 1$) тоонууд байна. Оройнууд $0$-ээс $n - 1$ хүртэл дугаарлагдсан байна. Модны үндэс нь $0$ дугаартай байна.

Гаралт

Тест бүрт хамгийн сүүлд үлдэх тоог шинэ мөрөнд хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4

3
-1 1 2
10
5

5
-1 1 2
-1 3 4
10
5
20

7
-1 1 2
-1 3 4
-1 5 6
1
2
3
4

11
-1 1 2
-1 3 4
-1 5 6
-1 7 8
15
7
-1 9 10
7
8
9
11
Гаралт
10
10
4
8
Сэтгэгдлүүдийг ачааллаж байна...