Через \textbf{G(S)} позначимо суму елементів множини \textbf{S} і \textbf{F(n)} являє собою суму \textbf{G(S)} для усіх підмножин множини, яка складається з перших \textbf{n} натуральних чисел. Наприклад, \textbf{F(3)} = \textbf{(1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24}. Для заданого \textbf{n} необхідно обчислити \textbf{F(1) + F(2) + ... + F(n)}. \InputFile Перший рядок містить кількість тестів \textbf{T} (\textbf{T} ≤ \textbf{1000}). Кожен з наступних \textbf{T} рядків містить ціле число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000000000}). \OutputFile Вивести \textbf{T} рядків, по одному числу у рядку для кожного відповідного тесту. Так як відповідь може бути дуже великою, виводьте відповідь по модулю \textbf{8388608}.