Background

What? What is a rhombus tree??

Alright, this is a very simple graph made by a newbie (pinyin: juruo) messing around. It is not a tree, but it looks a lot like a tree.

Like this.

(Alright, the picture is a bit large (and empty).)

Problem Description

You are given $T$ rhombus trees. For the $i$-th rhombus tree, the number of levels is $n_i$. Please compute the sum of the shortest path lengths over all pairs of points in the rhombus tree.

Input Format

The first line contains a positive integer $T$.

The next $T$ lines each contain a positive integer $n_i$, representing the size of the rhombus tree.

Output Format

Output $T$ lines. Each line contains one integer, representing the sum of the shortest path lengths over all pairs of points in the current rhombus tree, modulo $998244853$.

5
1
2
3
4
5

0
4
43
225
812

Hint

${\rm Subtask\ 1(10\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 10$.

${\rm Subtask\ 2(20\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 100$.

${\rm Subtask\ 3(30\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 1000$.

${\rm Subtask\ 4(40\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 5*10^6$.

To prevent precomputation with a lookup table, the memory limit is reduced to 64 MB.

Translated by ChatGPT 5