У лівому нижньому куті квадратної шахової дошки знаходиться король. Він може ходити лише на одну клітинку праворуч, вгору, чи по діагоналі праворуч вгору. Порахуйте кількість способів, якими король може дійти до правої верхньої клітинки дошки за модулем .
Перший рядок містить кількість тестів . Наступні рядків містять по одному цілому числу .
Для кожного значення виведіть шукану кількість способів.