В левом нижнем углу квадратной шахматной доски n×n находится король. Он может ходить только на одну клетку вправо, вверх, или вправо вверх. Посчитайте количество способов, которыми король может дойти до правой верхней клетки доски по модулю 1000003.
Первая строка входа содержит число T (1 ≤ T ≤ 10000) — количество тестов. Следующие T строк содержат по одному целому числу n (1 ≤ n ≤ 10^6).
Для каждого n выведите одно целое число — ответ на задачу.