İkilik qarşı mənfi ikilik

Negativ ikili sistem, əsası -2 olan bir mövqe sistemidir. Bu sistemdə, ikili sistemdə olduğu kimi, hər hansı bir qeyri-mənfi tam ədədi ifadə etmək mümkündür. Məsələn, 3_10 = 111_{-2}. Ancaq negativ ikili sistem mənfi ədədləri də müsbət ədədlər qədər asanlıqla ifadə edə bilir: -3_10 = 1101_{-2}. Bəzi ədədlər hər iki sistemdə eyni şəkildə ifadə olunur. Bu tapşırıqda biz ikili və negativ ikili sistemlərdə eyni təmsilata malik olan n-ci tam ədədi tapmaq istəyirik.

Giriş verilənləri

Giriş faylının ilk sətiri testlərin sayını göstərir. Hər bir test bir tam ədəd N (1 < N ≤ 10^9) ilə təmsil olunur və ayrı bir sətirdə verilir.

Çıxış verilənləri

Hər bir test üçün ikili və negativ ikili sistemlərdə eyni təmsilata malik olan n-ci tam ədəd ayrı bir sətirdə göstərilməlidir.

Nümunələr