T800633 Tidal Lighthouse

On the cliffs of Kaer stands a lighthouse. Its beacon sits at the centre of the tower, and every year the masons add one lamp niche above it and one below, so the tower is always symmetric about the beacon: **in year $k$ it holds $2k-1$ niches.** The lamps of Kaer burn with a cold, greedy flame. If two adjacent niches are lit on the same night their beams interfere and the whole tower goes dark, so the keeper must choose his pattern with care — any subset of niches, the empty one included, so long as no two chosen niches are neighbours. The keeper is old now. His logbook devotes one page to each year of his service, and on that page he wrote down *every* pattern that would have been legal that year. He wants to know how many patterns are written in the whole book.

In year $k$ the tower has $2k-1$ niches in a vertical line, numbered $1$ to $2k-1$. A **pattern** for year $k$ is a subset $P\subseteq\{1,\dots,2k-1\}$ containing no two consecutive integers. Let $w(k)$ be the number of such patterns. Given $n$, compute $$S(n)=\sum_{k=1}^{n} w(k) \pmod{998244353}.$$ There are $T$ independent queries.

Line 1: integer $T$. Next $T$ lines: one integer $n$ each.

$T$ lines, $S(n)\bmod 998244353$.

**Explanation for sample one:** Year 1: one niche, patterns $\varnothing,\{1\}$, so $w(1)=2$. Year 2: three niches, $w(2)=5$, running total $7$. Year 3: five niches, $w(3)=13$, total $20$. For all data: $1\le T\le 10^5$, $1\le n\le 10^{18}$. | Subtask | Points | $n\le$ | $T\le$ | |---|---|---|---| | 1 | 8 | $10$ | $10$ | | 2 | 12 | $10^6$ | $10$ | | 3 | 15 | $10^6$ | $10^5$ | | 4 | 20 | $10^{18}$ | $1$ | | 5 | 45 | $10^{18}$ | $10^5$ |