Generate all stick lengths obtainable from every a_i, along with the number of steps required to obtain it. From all lengths obtainable from all a_i, pick the one obtainable in the smallest total number of steps.

The main question is: how many distinct stick lengths are obtainable from a stick of length L?

In fact, this number is . It can be seen as follows. While L is even, divide it by 2 until it's odd. When it's odd, we'll have two possible stick lengths on the next step, let's denote them by X and X + 1.

What stick lengths are obtainable on the next step? They are X / 2, (X + 1) / 2 and (X + 2) / 2 (integer division). Clearly, X / 2 and (X + 2) / 2 differ by exactly one, and (X + 1) / 2 is equal to one of them. Thus, on the next step, we'll still have only two possible stick lengths. Since the number of steps is , the number of obtainable stick lengths is at most .

This is a DP problem. The only trouble is that A_i can be up to 10⁹.

Divide all integers from L₁ to R_n into segments such that all integers in this segment belong to the same set of ranges [L_i;R_i]. For example, if the ranges are [1;10], [3;10] and [8;15], then we'll form segments [1;2], [3;7], [8;10] and [11;15]. Clearly, we'll form at most 2n such segments.

Now, for every i, instead of deciding the value of A_i, let's only decide which segment it belongs to. Since A_i must be an increasing sequence, corresponding segment IDs must be non-decreasing.

For a fixed assignment of A_i to segments, how many ways are there to actually choose all A_i so that the conditions are satisfied? Well, it's the product of , where len_j is the length of the j-th segment, and cnt_j is the number of A_i belonging to the j-th segment.

This leads to a DP solution. Let f_i, k be the number of ways to assign the first i numbers to the first k segments. Transitions are done by looping over how many numbers are assigned to the next segment. The complexity is O(n³) (if you precalculate in advance or quickly calculate them during the process).

The solution is a somewhat straightforward application of Burnside's lemma.

For every even permutation p, we count the number of graphs left invariant by p. Then we know the answer.

Let's count such graphs for a given p. Suppose we have edges for all i in our directed graph. Fix some i. We have an edge . Since the graph is left invariant by p, we must have an edge in our graph. Similarly, we must have an edge too, and so on. Suppose that i belongs to a cycle of length ki in p. Then, we must have an edge . Since pkii = i, and we only have one edge outgoing from each vertex, we must have pkiai = ai. Thus, ai must belong to a cycle in p of length kai which is a divisor of ki.

This is a necessary condition. But if on every cycle in p we pick one i and choose a_i so that this condition is satisfied, then we can deduce the outgoing edges from all vertices on this cycle, and the condition will be satisfied for these vertices, too. It can be seen that this is also sufficient -- with the condition satisfied, there is a bijection between the original and the permuted vertices and edges, so that's an automorphism.

Hence, once we know the lengths of cycles in p, we can easily count graphs left invariant by p in polynomial time. Every distribution of cycle lengths is a partition of n, and there are not too many partitions for n ≤ 50, so we can try them all.

For every element of S, apply halving to it while it's larger than T. If it turns out to be equal to T after that, add 1 to the answer.

This is a DP problem.

Let f_i, j be the number of increasing sequences A₁, A₂, ..., A_i such that A_i = j. Clearly, if j < L_i or j > R_i, then f_i, j = 0. Otherwise, .

The problem is that this solution is too slow -- it works in O(n·max(R_i)²).

To fix that, note that . Thus, if both j and j - 1 belong to [L_i;R_i], then f_i, j = f_{i, j - 1} + f_{i - 1, j - 1}. We can calculate f_i, Li first in O(L_i) time, and then calculate f_i, j for j from L_i + 1 to R_i in O(1) time each.

This way, the solution works in O(n·max(R_i)), which is just enough to get accepted.

The key insight is: by applying twirls, we can permute the labels of the graph almost arbitrarily. In fact, we can apply any even permutation to the labels, since every twirl is equivalent to performing two transpositions.

The solution is: loop over all even permutations of length n and permute vertices of the graph according to them. Count the number of distinct graphs obtained using any equivalent of hashset. The complexity of this solution is about O(n!·n).