解题思路

给定一个“洞数”$k$。我们只统计满足如下条件的非负整数的个数：

• 不含前导 0（唯一允许为 0 本身）；
• 数位只由数字 0、8 组成；
• 数位“洞数”之和恰为 $k$。其中 0 记 1 个洞，8 记 2 个洞。

设答案为 $f(k)$。

题目内容

小苯对数字的洞数十分感兴趣，众所周知 $0$ 有 $1$ 个"洞”，而 $8$ 有 $2$ 个

现在他想知道，有多少个非负整数满足:

• 不包含前导 $0$ 。

• 其数位仅由 $0$ 和 $8$ 两种数字构成。

• 其“洞数”(一个整数的洞数定义为其各个数位所含洞数的总和)恰好为 $k$ 。

请你来算一算吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤T≤ 10^4)$ 代表数据组数，每组测试数据描述如下:

第一行输入一个正整数 $k(1 ≤ k≤ 10^9)$ 表示小苯询问的"洞数”。

输出描述

对于每组测试数据:

在单独的一行输出一个整数，表示合法的数字个数。

(由于结果可能很大，因此输出结果对 $998244353$ 取模的值。)

样例1

输入

5
1
4
10
100
1000

输出

1
2
34
750033655
407824689

说明

只有一个“洞”的合法数字，只有 $0$ 这一个。