Una permutación es una secuencia de enteros desde ~1~ hasta ~n~ de longitud ~n~, donde cada número aparece exactamente una vez. Por ejemplo, ~[1]~, \([4, 3, 5, 1, 2]\), \([3, 2, 1]\) son permutaciones, pero \([1, 1]\), \([4, 3, 1]\), \([2, 3, 4]\) no lo son.

Se dice que una permutación de longitud ~n~ es casi creciente si solo existe un único ~k~ con ~1 \le k \leq n-1~ tal que ~a_{k}>a_{k+1}~. Debes responder ~t~ preguntas: ¿cuántas permutaciones casi crecientes hay de longitud ~n~?

Subtareas

En todas las subtareas se cumple que ~t \leq 20~

• Subtarea 1 (6 puntos): ~n \leq 10~ .
• Subtarea 2 (31 puntos): ~n \leq 2000~ .
• Subtarea 3 (31 puntos): ~n \leq 2 \cdot 10^{5}~.
• Subtarea 4 (32 puntos): ~n \leq 10^{12}~.

Entrada

En la primera línea ~t \leq 20~, el número de casos.

En cada una de las ~t~ líneas hay un entero ~1 \leq n \leq 10^{12}~ el número de elementos en la permutación.

Salida

Para cada caso imprima un entero módulo ~998244353~: la cantidad de permutaciones casi crecientes de longitud ~n~.

Ejemplos

Entrada 1

3
2
4
87

Salida 1

1
11
982023288