Для положительного целого числа $$$a$$$ определим рекурренту $$$\{b_n\}_{n\geq 0}$$$ как $$$b_n = a^{b_{n-1}}$$$, при этом $$$b_0 = 1$$$.
Назовем положительное целое число $$$a$$$ $$$m$$$-тетрированным, если последовательность $$$b$$$ стабилизируется в значении $$$1$$$ по модулю $$$m$$$, то есть существует $$$N \ge 0$$$, такое что $$$b_n \equiv 1 \pmod m$$$ для всех $$$n \geq N$$$.
Для данного $$$m$$$ вычислите плотность $$$m$$$-тетрированных целых чисел. Здесь плотность множества $$$S$$$ — это предел $$$$$$\lim\limits_{n\rightarrow \infty}\frac{|S\cap [1,2,\ldots,n]|}{n}.$$$$$$ Неформально, это «доля» всех целых положительных чисел, которые являются $$$m$$$-тетрированными.
Можно показать (в ограничениях данной задачи), что плотность хорошо определена и всегда является рациональным числом, знаменатель которого не делится на $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Число $$$m$$$ будет дано вам как произведение трех целых чисел $$$x$$$, $$$y$$$ и $$$z$$$. Первая и единственная строка каждого набора входных данных содержит три целых числа $$$x$$$, $$$y$$$, $$$z$$$ ($$$1\leq x,y,z \leq 10^6$$$, $$$m = xyz \geq 2$$$).
Для каждого набора входных данных выведите плотность $$$m$$$-тетрированных целых чисел ($$$a$$$, для которых соответствующая последовательность $$$b_n$$$ сходится к $$$1$$$ по модулю $$$m$$$), по модулю $$$998\,244\,353$$$.
Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что точный ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x \lt M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.
55 1 15 2 123 1 110 10 29 3 37
499122177299473306893685162913393583705965601
В первом наборе входных данных $$$m = 5$$$. Например, $$$a=1$$$ является $$$5$$$-тетрированным, так как $$$b_n = 1$$$ для всех $$$n$$$. Для $$$a= 8$$$ последовательность $$$b$$$ равна $$$[1, 8, 8^8, 8^{(8^8)}, \ldots]$$$, что соответствует $$$[1, 3, 1, 1, \ldots]$$$ по модулю $$$5$$$. Можно доказать, что последовательность всегда равна $$$1 \pmod 5$$$ для достаточно больших $$$n$$$, так что $$$8$$$ является $$$5$$$-тетрированным. Для $$$a=10$$$ последовательность $$$b$$$ равна $$$[1, 10, 10^{10}, 10^{(10^{10})}, \ldots]$$$, что соответствует $$$[1, 0, 0, 0, \ldots]$$$ по модулю $$$5$$$. Можно доказать, что последовательность всегда равна $$$0 \pmod 5$$$ для достаточно больших $$$n$$$, так что $$$10$$$ не является $$$5$$$-тетрированным. Ответ для первого теста — $$$\frac{1}{2}$$$.
Во втором наборе входных данных $$$m= 10$$$, и ответ — $$$\frac{1}{10}$$$.
В третьем наборе входных данных $$$m= 23$$$, и ответ — $$$\frac{63}{506}$$$.
В четвертом наборе входных данных $$$m= 200$$$, и ответ — $$$\frac{1}{200}$$$.
В пятом наборе входных данных $$$m= 999$$$, и ответ — $$$\frac{1}{222}$$$.
