Teraz znajdujesz się w HSFZ, słynnym królestwie matematyki. Dlatego musisz rozwiązać kilka problemów matematycznych. Dane są dwie dodatnie liczby całkowite $p$ i $q$. Twoim zadaniem jest skonstruować dodatnie liczby całkowite $a, b, c, d$ takie, że $1 \le a, b, c, d \le 10^7$ oraz $$ \frac{a^3 + b^3}{c^3 + d^3} = \frac{p}{q} $$

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^6$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego, pojedynczy wiersz zawiera dwie liczby całkowite $p, q$ ($1 \le p, q \le 10^4$).

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający cztery liczby całkowite $a, b, c, d$ ($1 \le a, b, c, d \le 10^7$). Można wykazać, że przy powyższych ograniczeniach rozwiązanie zawsze istnieje.

Przykład

Wejście 1

2
1 1
9 28

Wyjście 1

1 1 1 1
1 2 1 3