POLSKI SPOJ

Jak nakazuje tradycja, co roku na Mistrzostwach Warszawskiej Wyższej Szkoły Informatyki w Programowaniu jest przynajmniej jedno zadanie kompletnie pozbawione historyjki. W tym roku padło na to, które właśnie czytasz. Dla liczby podanej na wejściu, wygeneruj niemalejący ciąg zgodny z zasadami ciągu Fibonacciego. Ostatnim elementem wygenerowanego ciągu Fibonacciego powinna być wczytana liczba. Zależy nam również, aby wygenerowany ciąg miał jak najwięcej elementów. Dla wygenerowanego ciągu wypisz jego dwa pierwsze elementy. Jeżeli istnieje więcej niż jedno rozwiązanie wybieramy to z najmniejszym pierwszym elementem ciągu.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 10⁵) określająca liczbę zestawów danych.

W kolejnych Z liniach znajdują się zestawy danych. Każdy z nich składa się z jednej liczby całkowitej n (1 ≤ n ≤ 2 × 10⁹) dla której mamy wygenerować odpowiedni ciąg.

Wyjście

Dla każdego zestawu danych należy wypisać w osobnej linii dwie liczby rozpoczynające szukany ciąg.

Przykład

Wejście:

3
10
17
4181

Wyjście:

0 2
1 5
0 1