P4834 Satania's Final Exam

"Hey, Gabriel, where should we go to have fun during summer vacation?" Vignette patted Gabriel on the shoulder. "Huh? Of course I'll stay home and play games during summer vacation," Gabriel replied listlessly. "You can't do that. You're an angel at least—act like one." "What a pain." "So, how about we go to the beach during summer vacation?" "Agreed, agreed! If we go to the beach, I can tease Gabriel to my heart's content," Raphiel slipped in before anyone noticed. "Such a pain." While everyone was discussing where to go for summer vacation, Satania listened on the side feeling conflicted, because no one had invited her. "Heh heh heh, I am the great demon Satania. How could I possibly join them on my own? I must wait for them to invite me," Satania schemed to herself. "Hey, I think Satania looks a little unhappy." "It's more than 'looks like'—she's not even trying to hide that expression." "Hey, should we invite her?" Raphiel said this as she walked over to Satania. "Satania-san, we're going to the beach during summer vacation~" "Heh heh heh, finally here to invite me?" Satania muttered softly, a little pleased. "Satania-san, please stay right here obediently~" "Uh..." Satania took massive psychological damage. "Hey, what do you think you're doing?" "Hm? Because, Satania-san, if you want to go out and play during summer vacation, you have to pass the final exams, or else you'll be kept for remedial classes." "Re... remedial..." Satania seemed to realize something, her face changed dramatically. "Remedial... hey, Raphiel... c-can you tutor me?" "Hm? Sure~ But how you do on the finals depends on you." "Thanks. Then could you check where I got these wrong? I don't understand at all." "Let me see..." Raphiel left Gabriel and Vignette and started tutoring Satania alone. Finally, the finals arrived. Satania had worked hard for so long; it all came down to this exam! After sustained effort, everything on the finals went smoothly—apart from the math exam that hadn’t happened yet, she passed all the other subjects! At last came the final test—the physics exam. The good news was that Satania had already answered 59 points worth of questions, all correct. But then she ran into a fiendishly difficult problem, and to her amazement, with a total of 100 points, this problem alone was worth 41. If she left it blank, she would fail. "If anyone fails any subject in the finals, that person must attend remedial classes and make-up exams during summer vacation!" The homeroom teacher’s words echoed in her ears. What should she do...

This problem is as follows: There is an electric field formed by $n$ point charges. Assume each point charge produces a uniform electric field rather than a point-charge field, and the $i$-th point charge has field strength $E_i=i$. Now place a negatively charged test charge in this field. As soon as the test charge touches any point charge, it will "fuse" with that point charge and release a huge amount of energy. Because the field strengths produced by the point charges differ, the test charge is attracted to each point charge with different force; the stronger the attraction a point charge exerts on the test charge, the greater the probability of being drawn to that point charge, and the probability is proportional to the attraction. Assume the smallest point charge exerts attraction $F$ on the test charge. Then another point charge exerts $iF$. Suppose the probability of touching the smallest point charge is $P$. Then the probability for each point is $iP$. After touching a point charge, the released energy is $\mathrm{Fib}(E_i)$. Find the expected released energy. The good news is that as long as she gets points on this problem, Satania will pass!

The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines contains an integer $n$, the number of point charges.

For each query, output one integer representing the expected energy. To avoid precision issues, please output the answer modulo $998{,}244{,}353$.

- Sample Explanation $\dfrac{1}{3}\times \mathrm{Fib}(1)+\dfrac{2}{3}\times \mathrm{Fib}(2)=1$. Please read the problem carefully along with the sample. - Constraints - For $10\%$ of the testdata, $T=1$, $n=2$. - For $30\%$ of the testdata, $T \le 10$, $1 \le n \le 10^6$. - For $60\%$ of the testdata, $T \le 10^6$, $1 \le n \le 10^6$. - For $100\%$ of the testdata, $T \le 10^6$, $1 \le n \le 10^9$, and it is guaranteed that $n \ne 998244352$ and $n \ne 998244353$. $\mathrm{Fib}(i)$ is the Fibonacci sequence. $$\mathrm{Fib}(i)=\begin{cases} 1 & i\le 2 \cr \mathrm{Fib}(i-1)+\mathrm{Fib}(i-2) & i > 2 \end{cases}$$ Translated by ChatGPT 5