解题思路
本题要求计算满足约束条件的步长序列数量。约束为：每一步可以是 1 米或 2 米，总距离恰好为 k 米；必须保证第一步不是 1 米，除非整个序列只有一步（即 k=1，此时步长为 1 米是允许的）。
-
特判 k=1：只有一种方案 [1]，故答案为 1。
-
对于 k≥2，由于第一步不能是 1，第一步必须是 2 米。第一步走完后，剩余距离为 k−2 米。剩余部分可以任意使用 1 米和 2 米的步长，没有任何额外限制。
-
定义 g(n) 为用 1 米和 2 米的步长走完 n 米的总方案数（步长顺序不同视为不同方案）。显然有：
题目内容
小 R 正在设计一套健身计划。他每次可以选择迈出一步，步长可以是 1 米或 2 米。他想完成总距离恰好为 k 米的训练，并且规定：第一步不能迈 1 米，除非整个计划只包含一步（即 k=1 时允许第一步迈 1 米）。请你计算有多少种不同的步长序列可以实现他的计划，序列的顺序不同视为不同的方案。由于答案可能很大，请输出对 998244353 取模的结果。
约束：k 是正整数，满足 1≤k≤109；测试数据组数 T 满足 1≤T≤104。
输入描述
第一行包含一个整数 T (1≤T≤104)，表示测试数据组数。接下来 T 行，每行包含一个整数 k (1≤k≤109)，表示目标总距离。
输出描述
