CF1770D Koxia and Game

Koxia and Mahiru are playing a game with three arrays $ a $ , $ b $ , and $ c $ of length $ n $ . Each element of $ a $ , $ b $ and $ c $ is an integer between $ 1 $ and $ n $ inclusive. The game consists of $ n $ rounds. In the $ i $ -th round, they perform the following moves: - Let $ S $ be the multiset $ \{a_i, b_i, c_i\} $ . - Koxia removes one element from the multiset $ S $ by her choice. - Mahiru chooses one integer from the two remaining in the multiset $ S $ . Let $ d_i $ be the integer Mahiru chose in the $ i $ -th round. If $ d $ is a permutation $ ^\dagger $ , Koxia wins. Otherwise, Mahiru wins. Currently, only the arrays $ a $ and $ b $ have been chosen. As an avid supporter of Koxia, you want to choose an array $ c $ such that Koxia will win. Count the number of such $ c $ , modulo $ 998\,244\,353 $ . Note that Koxia and Mahiru both play optimally. $ ^\dagger $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq {10}^5 $ ) — the size of the arrays. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ ). The third line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \leq b_i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ {10}^5 $ .

Output a single integer — the number of $ c $ makes Koxia win, modulo $ 998\,244\,353 $ .

In the first test case, there are $ 6 $ possible arrays $ c $ that make Koxia win — $ [1, 2, 3] $ , $ [1, 3, 2] $ , $ [2, 2, 3] $ , $ [2, 3, 2] $ , $ [3, 2, 3] $ , $ [3, 3, 2] $ . In the second test case, it can be proved that no array $ c $ makes Koxia win.