CF2147G Modular Tetration

For a positive integer $ a $ , we define a recurrence $ \{b_n\}_{n\geq 0} $ as $ b_n = a^{b_{n-1}} $ , with $ b_0 = 1 $ . We say that a positive integer $ a $ is $ m $ -tetrative if the sequence $ b $ stabilizes to $ 1 $ modulo $ m $ , that is, there exists $ N \ge 0 $ such that $ b_n \equiv 1 \pmod m $ for all $ n \geq N $ . For a given $ m $ , calculate the density of the $ m $ -tetrative integers. Here, the density of a set $ S $ is the limit $$$ \lim\limits_{n\rightarrow \infty}\frac{|S\cap [1,2,\ldots,n]|}{n}. $$$ Informally, it is the "proportion" of positive integers that are $ m $ -tetrative. It can be proven (under the constraints of this problem) that the density is well-defined and is always a rational number, whose denominator is not divisible by $ 998\,244\,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The number $ m $ will be given to you as a product of three integers $ x $ , $ y $ , and $ z $ . The first and only line of each test case contains three integers $ x $ , $ y $ , $ z $ ( $ 1\leq x,y,z \leq 10^6 $ , $ m = xyz \geq 2 $ ).

For each test case, print the density of $ m $ -tetrative integers ( $ a $ such that its corresponding sequence $ b_n $ converges to $ 1 $ modulo $ m $ ), modulo $ 998\,244\,353 $ . Formally, let $ M = 998\,244\,353 $ . It can be shown that the exact answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .

In the first test case, $ m = 5 $ . For example, $ a=1 $ is $ 5 $ -tetrative since $ b_n = 1 $ for all $ n $ . For $ a= 8 $ , the sequence $ b $ is $ [1, 8, 8^8, 8^{(8^8)}, \ldots] $ , which is $ [1, 3, 1, 1, \ldots] $ if we look at it modulo $ 5 $ . It can be proven that the sequence is always $ 1 \pmod 5 $ for big enough $ n $ , so $ 8 $ is $ 5 $ -tetrative. For $ a=10 $ , the sequence $ b $ is $ [1, 10, 10^{10}, 10^{(10^{10})}, \ldots] $ , which is $ [1, 0, 0, 0, \ldots] $ if we look at it modulo $ 5 $ . It can be proven that the sequence is always $ 0 \pmod 5 $ for big enough $ n $ , so $ 10 $ is not $ 5 $ -tetrative. The answer for the first test case is $ \frac{1}{2} $ . In the second test case, $ m= 10 $ and the answer is $ \frac{1}{10} $ . In the third test case, $ m= 23 $ and the answer is $ \frac{63}{506} $ . In the fourth test case, $ m= 200 $ and the answer is $ \frac{1}{200} $ . In the fifth test case, $ m= 999 $ and the answer is $ \frac{1}{222} $ .