构造字符串

题目描述

小 Z 最近对构造字符串特别感兴趣，他想知道要构造一个长度为 $n$ 的满足以下条件的字符串 $s$：

• $s$ 由小写字母 $\tt a$ 至 $\tt z$ 构成；
• $s$ 中至少包含一个字母 $\tt a$ 以及一个字母 $\tt b$。

给定 $n$，试求出有多少个不同的满足条件的字符串 $s$，答案对 $998244353$ 取模。

输入格式

本题在单个测试点中有多组数据。

输入共 $T+1$ 行。

第 $1$ 行 $1$ 个整数，表示单个测试点中的数据组数 $T$。

接下来，对于每组数据，输入共 $1$ 行 $1$ 个整数，表示字符串 $s$ 的长度 $n$。

输出格式

输出共 $T$ 行。

对于每组数据，输出共 $1$ 行 $1$ 个整数，表示满足条件的字符串 $s$ 的数量，答案对 $998244353$ 取模。

样例 #1

样例输入 #1

3
2
3
114514

样例输出 #1

2
150
984497607

提示

【数据范围】

本题开启捆绑测试。

对于 $100\%$ 的数据，$1\le T\le10^5$，$1\le n\le10^{18}$。

$\text{Subtask}$	$T\le$	$n\le$	$\text{Score}$
$1$	$10$	$5$	$10$
$2$	$1$	$10^7$	$30$
$3$	$10^5$	$10^7$	$20$
$4$	$10^5$	$10^{18}$	$40$