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