Через \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}.