考虑一个长度为 $m$ 的字符串 $p$ 和一个长度为 $n$ 的字符串 $s$（其中 $n \ge m$）。如果存在一个整数 $k$，使得 $p^k$ 是 $ss$ 的前缀，且 $p^k$ 的长度大于或等于 $s$ 的长度，则称 $p$ 带进位覆盖 $s$。这里 $p^k$ 表示 $k$ 个 $p$ 的拼接。

你可以想象字符串 $s$ 写在一个圆环上，你从开头开始通过拼接 $p$ 的副本覆盖它，如果下一个副本超过了 $s$ 的末尾，它必须继续覆盖 $s$ 的开头部分。

例如，字符串 “01001001” 可以被字符串 “010” 带进位覆盖，但字符串 “1011011” 不能被 “101” 带进位覆盖，字符串 “10110101” 也不能。

一个字符串可以被多个其他字符串带进位覆盖。例如，字符串 “11111” 可以被任何长度为 1 到 5 且仅由 ‘1’ 组成的字符串带进位覆盖。我们用 $cc(s)$ 表示带进位覆盖 $s$ 的字符串的数量。例如，$cc(“11111”) = 5$ 且 $cc(“01001001”) = 2$。

考虑所有长度为 $n$、由字符 ‘0’ 和 ‘1’ 组成的字符串。求所有这些字符串的 $cc(s)$ 之和。结果对 $998\,244\,353$ 取模。

例如，当 $n = 3$ 时，$cc(“000”) + cc(“001”) + cc(“010”) + cc(“011”) + cc(“100”) + cc(“101”) + cc(“110”) + cc(“111”) = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 3 = 12$。

输入格式

输入文件包含多个测试用例。每个测试用例包含一行，为一个整数 $n$ ($1 \le n \le 1000$)。最后一个测试用例后跟一行包含零的行，该行不应被处理。

输出格式

对于每个测试用例，输出一个整数：所有长度为 $n$ 的二进制字符串的 $cc(s)$ 之和，对 $998\,244\,353$ 取模。

样例

输入 1

3
0

输出 1

12