Altçoxluqların cəmlənməsi

G(S) ilə S çoxluğunun elementlərinin cəmini işarə edək və F(n) ilk n natural ədədi ehtiva edən çoxluğun bütün altçoxluqları üçün G(S) cəmini əks etdirir. Məsələn, F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24. Verilmiş n üçün F(1) + F(2) + ... + F(n)- i hesablamaq lazımdır.

Giriş verilənləri

Birinci sətir T (T ≤ 1000) testlərin sayını ehtiva edir. Hər bir növbəti T sətri n (1 ≤ n ≤ 1000000000) tam ədədini ehtiva edir.

Çıxış verilənləri

Hər bir uyğun test üçün hər birində bir ədəd olmaqla T sətir verməli. Cavabın çox böyük ola biləcəyini nəzərə alaraq 8388608 moduluna görə verin.

Nümunələr