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:</p>

• 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.
  </li> </ul>

  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 l_i i r_i (1 ≤ l_i, r_i ≤ n) będące numerami lewego i prawego syna wierzchołka i. W przypadku gdy wierzchołek nie ma lewego syna, l_i = -1, a gdy nie ma prawego, r_i = -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.

  예제 입력

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

  예제 출력

  1
  2
  3
  4