시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Ostatnio Bajtek zobaczył w Bajternecie drzewo bajnarne. Drzewem bajnarnym nazywamy dowolne ukorzenione drzewo, w którym każdy wierzchołek ma 0, 1 lub 2 synów. Wysokością drzewa nazywamy liczbę wierzchołków na najdłuższej ścieżce od korzenia do pewnego z liści; drzewo puste ma wysokość 0. Na drzewach bajnarnych zdefiniowany jest porządek leksykograficzny. Drzewo A jest leksykograficznie mniejsze od drzewa B, gdy:

  • wysokość drzewa A jest mniejsza od wysokości drzewa B lub
  • wysokości drzew A i B są równe oraz:
    • lewe poddrzewo A jest leksykograficznie mniejsze niż lewe poddrzewo B lub
    • lewe poddrzewo A jest równe lewemu poddrzewu B i prawe poddrzewo A jest leksykograficznie mniejsze od prawego poddrzewa B.

Jeśli dany wierzchołek nie posiada lewego syna, to jego lewe poddrzewo uznajemy za drzewo puste; analogicznie w przypadku braku prawego syna.

Jeśli drzewa A i B są różne i drzewo A nie jest leksykograficznie mniejsze niż drzewo B, to drzewo A jest leksykograficznie większe niż drzewo B.

Twoje zadanie polega na wczytaniu opisu drzewa i obliczeniu numeru tego drzewa w porządku leksykograficznym. Drzewo składające się z jednego wierzchołka ma numer 1.

입력

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita t (1 ≤ t ≤ 1 000) będąca liczbą drzew. W kolejnych wierszach znajduje się t opisów drzew. W pierwszym wierszu opisu drzewa znajduje się jedna liczba całkowita n (1 ≤ n ≤ 2 000) będąca liczbą wierzchołków, z których składa się drzewo. Wierzchołki drzewa numerujemy liczbami od 1 do n, przy czym wierzchołek 1 jest korzeniem. Kolejne n wierszy opisuje krawędzie drzewa. i-ty z nich zawiera dwie liczby całkowite li i ri (1 ≤ li, rin) będące numerami lewego i prawego syna wierzchołka i. W przypadku gdy wierzchołek nie ma lewego syna, li = -1, a gdy nie ma prawego, ri = -1.

출력

Na standardowe wyjście należy wypisać dokładnie t wierszy zawierających jedną liczbę całkowitą będącą numerem odpowiedniego drzewa w zadanym porządku modulo 1 000 000 000.

예제 입력 1

4
1
-1 -1
2
-1 2
-1 -1
2
2 -1
-1 -1
3
2 3
-1 -1
-1 -1

예제 출력 1

1
2
3
4