题目描述

你有 n 个火柴棍，问用完所有的火柴棍可以摆出的最小的数（不含前导零，但可以为0）是多少？ 摆出 0~9 所需要的火柴棍如下图：

由于你能摆出的数字可能非常大，请输出对 998244353 取模的结果。

输入格式

第一行一个整数 T 表示数据组数。 对于每组数据输入一行一个整数 n 。

输出格式

于每组数据输出一行一个整数，表示答案。

样例输入

2
7
8

样例输出

8
10

数据规模及约定

对于前 30% 的数据，保证 $n \leq 20$ 。 对于前 50% 的数据，保证 $n \leq 60$。 对于前 70% 的数据，保证所有数据 n 的和不超过 $10^6$。 对于前 100% 的数据，保证$2 \leq n \leq 10^5$,$1 \leq T \leq 10^5$。