Döşəmə Plitələri#3337
Döşəmənizi kvadrat plitələrlə bəzəmək istəyirsiniz və düzbucaqları sevirsiniz. Altı kvadrat döşəmə plitəsindən istifadə edərək, dəqiq iki unikal düzbucaq yarada bilərsiniz: 1×6 və 2×3 (6×1 1x6 ilə, 3×2 isə 2×3 ilə eyni hesab olunur). Dörd kvadrat plitə ilə də bütün plitələrdən istifadə edərək dəqiq iki unikal düzbucaq yarada bilərsiniz: 1×4 və 2×2.
Verilmiş tam ədəd N üçün, bütün plitələrdən istifadə edərək dəqiq N unikal düzbucaq yaratmaq üçün lazım olan ən az kvadrat plitə sayını tapın və daha çoxunu yox. Məsələn, əgər N=2 olarsa, cavab 4-dür.
Girişdə bir neçə test halı olacaq. Hər bir test halı tək bir tam ədəd N (1 ≤ N ≤ 75) olan tək bir sətirdən ibarət olacaq, bu da istənilən düzbucaqların sayını təmsil edir. Giriş tək 0 olan bir sətirlə bitəcək.
Hər bir test halı üçün, bütün plitələrdən istifadə edərək dəqiq N düzbucaq yaratmaq üçün lazım olan ən az kvadrat döşəmə plitələrinin sayını təmsil edən tək bir tam ədəd çıxarın. Cavabın ən çox 10^18 olması təmin edilir. Əlavə boşluqlar çıxarmayın və cavabları boş sətirlərlə ayırmayın.
Nümunə 1