Суммирование подмножеств

Через G(S) обозначим сумму элементов множества S и F(n) представляет собой сумму G(S) для всех подмножеств множества, состоящего из первых n натуральных чисел. Например, F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24. Для заданного n необходимо вычислить F(1) + F(2) + ... + F(n).

Входные данные

Первая строка содержит количество тестов T (T ≤ 1000). Каждая из следующих T строк содержит целое число n (1 ≤ n ≤ 1000000000).

Выходные данные

Вывести T строк, по одному числу в строке для каждого соответствующего теста. Так как ответы могут быть очень большими, выводите ответ по модулю 8388608.

Примеры