2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) |
---|
Finished |
Peter loves folding segments. There is a segment on a number line occupying the interval $$$[\ell, r]$$$. Since it is the prime time for folding the segments, Peter decides to fold the segment carefully. In each step, he chooses one of the two following operations whenever possible:
A folding sequence refers to a sequence of operations specified above. Peter wants to fold the segment several times, resulting in the shortest possible interval whose length that cannot be further reduced. The length of an interval $$$[\ell, r]$$$ is defined naturally to be $$$r-\ell$$$. Let's consider the following example. Suppose that we are folding a segment initially occupying the interval $$$[1, 30]$$$. There are three folding sequences that lead to the shortest possible resulting interval, as shown in the following figure.
Please help Peter determine the number of folding sequences such that the resulting interval has a shortest possible length. Output the number modulo $$$998244353$$$.
$$$^{\text{∗}}$$$Recall that an integer $$$p>1$$$ is a prime number if there do not exist integers $$$a, b>1$$$ such that $$$p=ab$$$.
The first line contains an integer $$$t$$$, denoting the number of test cases. In each of the following $$$t$$$ lines, there are two integers $$$\ell$$$ and $$$r$$$.
For each test case, please output a line denoting the number of ways to fold the given segment such that the resulting segment has the shortest possible length, modulo $$$998244353$$$.
3 1 30 16 18 142857 240135
3 1 63
Name |
---|