P4976 God of “Duliu” TM Rhombus Tree - ②

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).)

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.

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 $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$.

${\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