H. Поток астеризма
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Bogocubic играет в игру с amenotiomoi. Сначала Bogocubic фиксировал целое число $$$n$$$, затем он дал amenotiomoi целое число $$$x$$$, изначально равное $$$1$$$.

За один ход amenotiomoi выполняет одну из следующих операций с равной вероятностью:

  • увеличить $$$x$$$ на $$$1$$$;
  • умножить $$$x$$$ на $$$2$$$.

Bogocubic хочет узнать, чему равно математическое ожидание числа шагов, которое должен сделать amenotiomoi, чтобы сделать $$$x$$$ больше или равным $$$n$$$. Найдите эту величину по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$y$$$, что $$$0 \le y < M$$$ и $$$y \cdot q \equiv p \pmod{M}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

Выходные данные

Для каждого набора входных данных выведите одно число — математическое ожидание числа шагов по модулю $$$998\,244\,353$$$.

Пример
Входные данные
7
1
4
8
15
998244353
296574916252563317
494288321850420024
Выходные данные
0
499122179
717488133
900515847
93715054
44488799
520723508
Примечание

В первом наборе входных данных $$$n\le x$$$ без выполнения каких-либо операций, так что ответ равен $$$0$$$.

Во втором наборе входных данных, для $$$n = 4$$$, ниже указан список всех возможных последовательностей операций вместе с вероятностями их реализации:

  • $$$1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$$$, вероятность равна $$$\frac{1}{8}$$$;
  • $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$$$, вероятность равна $$$\frac{1}{8}$$$;
  • $$$1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$$$, вероятность равна $$$\frac{1}{8}$$$;
  • $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$$$, вероятность равна $$$\frac{1}{8}$$$;
  • $$$1\stackrel{+1}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$$$, вероятность равна $$$\frac{1}{4}$$$;
  • $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$$$, вероятность равна $$$\frac{1}{4}$$$.

Значит, математическое ожидание числа шагов равно $$$4 \cdot \left(3 \cdot \frac{1}{8}\right) + 2 \cdot \left(2 \cdot \frac{1}{4} \right) =\frac{5}{2} \equiv 499122179 \pmod{998244353}$$$. В третьем наборе входных данных, для $$$n = 8$$$, математическое ожидание числа шагов равно $$$\frac{137}{32}\equiv 717488133\pmod{998244353}$$$.

В четвёртом наборе входных данных, для $$$n = 15$$$, математическое ожидание числа шагов равно $$$\frac{24977}{4096} \equiv 900515847 \pmod{998244353}$$$.