Rak n Roll

Trener Jerzy ułożył swojemu podopiecznemu plan treningowy na kolejne n dni. Jego zawodnik Mariusz każdego dnia ma realizować jeden z czterech rodzajów treningów biegowych. Niestety Jerzy to perfekcjonista i nigdy nie jest do końca zadowolony ze swojej pracy, podobnie jest i tym razem.

Nasz bohater uznał, że plan treningowy Mariusza powinien być jak najbardziej zróżnicowany. Formalnie rzecz ujmując - każdy spójny podciąg ciągu n treningów musi zawierać maksymalną liczbę rodzajów treningów.

Jerzy zdecydował się przerobić swój plan, tak aby spełniał to założenie. Jest tylko jeden problem, Mariusz zdążył się już oswoić z dotychczasową wersją i na pewno nie będzie zadowolony kiedy usłyszy o zmianach. W związku z tym nasz bohater postanowił, że liczba modyfikacji treningów niezbędnych do spełnienia jego nowego założenia powinna być minimalna.

Twoim zadaniem jest przerobienie planu treningowego Jerzego, tak aby spełniał powyższe wytyczne.

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t ∈ [1, 70000]. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych zawiera jeden wyraz składający się z cyfr z przedziału [1, 4] określających rodzaje kolejnych treningów w dotychczasowej wersji planu Jerzego. Długość wyrazu zawiera się w przedziale [4, 10⁵].

Gwarantujemy, że suma długości wszystkich wyrazów nie przekracza 10⁶.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać przerobiony plan treningowy Jerzego, spełniający nowe założenia. Jeżeli istnieje wiele rozwiązań wypisz dowolne z nich.

Przykład

Wejście:

3
24313241
2413
14442

Wyjście:

24312431
2413
12341