Maximum Set
Contest: Educational Codeforces Round 144 (Rated for Div. 2)
Difficulty rating: 1600
Tags: binary search, math

A set of positive integers $$$S$$$ is called beautiful if, for every two integers $$$x$$$ and $$$y$$$ from this set, either $$$x$$$ divides $$$y$$$ or $$$y$$$ divides $$$x$$$ (or both).

You are given two integers $$$l$$$ and $$$r$$$. Consider all beautiful sets consisting of integers not less than $$$l$$$ and not greater than $$$r$$$. You have to print two numbers:

- the maximum possible size of a beautiful set where all elements are from $$$l$$$ to $$$r$$$;
- the number of beautiful sets consisting of integers from $$$l$$$ to $$$r$$$ with the maximum possible size.

Since the second number can be very large, print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases.

Each test case consists of one line containing two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^6$$$).

Output format:
For each test case, print two integers — the maximum possible size of a beautiful set consisting of integers from $$$l$$$ to $$$r$$$, and the number of such sets with maximum possible size. Since the second number can be very large, print it modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the maximum possible size of a beautiful set with integers from $$$3$$$ to $$$11$$$ is $$$2$$$. There are $$$4$$$ such sets which have the maximum possible size:

- $$$\{ 3, 6 \}$$$;
- $$$\{ 3, 9 \}$$$;
- $$$\{ 4, 8 \}$$$;
- $$$\{ 5, 10 \}$$$.

Example input:
4
3 11
13 37
1 22
4 100

Example output:
2 4
2 6
5 1
5 7

Editorial:
Every beautiful set can be represented as a sequence of its elements in sorted order. Let these elements for some set be $$$a_1, a_2, \dots, a_m$$$; also, let $$$d_i = \frac{a_{i+1}}{a_i}$$$. When the set is beautiful, every $$$d_i$$$ is an integer greater than $$$1$$$.
It's easy to see that if $$$a_1$$$ and $$$a_m$$$ belong to $$$[l, r]$$$, the whole set belongs to $$$[l, r]$$$. Since $$$a_m = a_1 \cdot \prod \limits_{i=1}^{m-1} d_i$$$, in order to maximize $$$m$$$, we need to choose $$$a_1$$$ and $$$d_i$$$ as small as possible. So, why don't we choose $$$a_1 = l$$$ and every $$$d_i = 2$$$? This will allow us to calculate the maximum possible size of a beautiful set (let $$$m$$$ be this maximum possible size).
Okay, what about counting those sets? The claims $$$a_1 = l$$$ and that every $$$d_i = 2$$$ are no longer true by default. However, there are some constraints on $$$d_i$$$.
Firstly, every $$$d_i \le 3$$$. If we had some value of $$$d_i \ge 4$$$, we could replace it with two values of $$$d_i = 2$$$, and the size of the set would increase.
Secondly, there is at most one $$$d_i = 3$$$. If there are two values $$$d_i = 3$$$, we could replace them with three $$$d_i = 2$$$, and the size of the set would increase as well.
So, the sequence $$$d_i$$$ contains at most one value $$$3$$$, and the rest of the values are $$$2$$$.
We will divide the sets we want to count into two categories: the ones with all $$$d_i = 2$$$, and the ones with one value $$$d_i = 3$$$.
To count the sets in the first category, we simply need to count the number of different minimum values in those sets. Those minimum values have to be such that multiplying them by $$$2^{m-1}$$$ wouldn't make them greater than $$$r$$$, so these are all integers from the segment $$$[l, \lfloor \frac{r}{2^{m-1}} \rfloor]$$$. For every such integer, there exists exactly one set of the first category.
To count the sets in the second category, we do a similar thing. The minimum value in the set should be from the segment $$$[l, \lfloor \frac{r}{2^{m-2} \cdot 3} \rfloor$$$; but for every integer from this segment, there are $$$m-1$$$ different sets of the second category since there are $$$m-1$$$ ways to choose which $$$d_i$$$ is equal to $$$3$$$.