Distinct Sub-palindromes

S is a string of length n. S consists of lowercase English alphabets.

Your task is to count the number of different S with the minimum number of distinct sub-palindromes. Sub-palindrome is a palindromic substring.

Two sub-palindromes u and v are distinct if their lengths are different or for some i (0≤i≤length), $u_i$≠$v_i$. For example, string “aaaa” contains only 4 distinct sub-palindromes which are “a”, “aa”, “aaa” and “aaaa”.

The first line contains an integer T (1≤T≤$10^5$), denoting the number of test cases.

The only line of each test case contains an integer n (1≤n≤$10^9$).

For each test case, output a single line containing the number of different strings with minimum number of distinct sub-palindromes.

Since the answer can be huge, output it modulo 998244353.