문제<\/h2>
The Towers of Hanoi<\/em> is a famous mathematical puzzle consisting of three rods and $n<\/mi><\/mrow>n<\/math><\/span><\/span> n<\/span><\/span><\/span><\/span> disks with diameters 1<\/mn>,<\/mo>2<\/mn>,<\/mo>\dots<\/mo>,<\/mo>n<\/mi><\/mrow>1, 2, \ldots, n<\/math><\/span><\/span> 1<\/span>,<\/span> <\/span> 2<\/span>,<\/span> <\/span> \dots<\/span> <\/span>,<\/span> <\/span> n<\/span><\/span><\/span><\/span>. Each of the three rods contains some disks, stacked in order of decreasing diameter from bottom to top, so that the smallest disk is always at the top. A valid move consists of taking the smallest disk from a rod and putting it on top of another rod. This move must preserve the sorted order: you can't put a larger disk onto a smaller one. The original puzzle's goal is to transfer all disks from one rod to another.<\/p> In this variation of the puzzle, you can only move the disks between adjacent rods<\/strong>: you can move a disk between rods 1<\/mn><\/mrow>1<\/math><\/span><\/span> 1<\/span><\/span><\/span><\/span> and 2<\/mn><\/mrow>2<\/math><\/span><\/span>$

[이미지 1]<\/span><\/td>	[이미지 2]<\/span><\/td>	[이미지 3]<\/span><\/td> <\/tr>
Valid move<\/td>	Invalid move: non-adjacent rods<\/td>	Invalid move: moving a larger disk onto a smaller one<\/td> <\/tr> <\/tbody> <\/table> Given two configurations of this puzzle, find the minimum number of moves required to reach the second configuration starting from the first one. As this number might be large, print it modulo $998<\/mn><\/mtext>244<\/mn><\/mtext>353<\/mn><\/mrow>998\,244\,353<\/math><\/span><\/span> 998<\/span> <\/span> 244<\/span> <\/span> 353<\/span><\/span><\/span><\/span>.<\/p> 입력<\/h2> Each test contains multiple test cases. The first line contains the number of test cases t<\/mi><\/mrow>t<\/math><\/span><\/span> t<\/span><\/span><\/span><\/span> (1<\/mn>\leq<\/mo>t<\/mi>\leq<\/mo>10<\/mn>3<\/mn><\/msup><\/mrow>1 \le t \le 10^3<\/math><\/span><\/span> 1<\/span> <\/span> \leq<\/span> <\/span><\/span> <\/span> t<\/span> <\/span> \leq<\/span> <\/span><\/span>$

Hanoi Towers Reloaded