Легион#3934
Legion — Qədim Roma ordusunun əsas təşkilati vahidi. Müxtəlif dövrlərdə legionlar fərqli sayda və müxtəlif düzülüşlərdə olmuşdur. Ən sadə düzülüş sıra idi. sayda legion əsgərindən ibarət sıradan üç nəfəri kəşfiyyata göndərmək üçün aşağıdakı əməliyyatlar yerinə yetirilirdi: əgər sıradakı əsgərlər üçdən çoxdursa, sıra iki yerə bölünürdü, biri cüt mövqelərdə dayanan əsgərlərdən, digəri isə tək mövqelərdə dayanan əsgərlərdən ibarət olurdu. Bu prosedur, hər birində üçdən çox əsgər qalmayana qədər bütün sıralar üçün təkrarlanırdı. Əgər üç əsgər qalmışdısa, bu qrupu kəşfiyyata göndərmək olardı.
Əsas sıradan neçə üç nəfərlik qrupun formalaşdırıla biləcəyini müəyyən etmək tələb olunur.
Giriş faylının ilk sətri ədədini ehtiva edir — testlərin sayı (T \leq 10^4). Növbəti sətrin hər biri tam ədədini ehtiva edir — sıradakı əsgərlərin sayı (0 \leq N \leq 10^{18}).
Hər bir test üçün ayrıca sətirdə bir tam ədəd çıxarılır — əsas sıradan formalaşdırılan üç nəfərlik qrupların sayı.
Nümunə 1