Maximum Set

题意翻译

定义一个集合 $S$ 是合法的，当且仅当集合中任意两个整数 $x$ 和 $y$ 满足 $x$ 被 $y$ 整除或 $y$ 被 $x$ 整除。 有 $t$ $(1\le t\le 2\times10^4)$ 次询问，每次给出整数 $l,r$ $(1\le l\le r \le 10^6)$，每次询问给出两个回答，第一个是在集合 $[l,r]$ 中选出整数组成的合法集合的最大大小，第二个是大小最大的合法集合的个数。

题目描述

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 $ .

输入输出格式

输入格式

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 $ ).

输出格式

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 $ .

输入输出样例

输入样例 #1

4
3 11
13 37
1 22
4 100

输出样例 #1

2 4
2 6
5 1
5 7

说明

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 \} $ .

**最大集合**

**题目大意：**
定义一个正整数集合 $ S $ 是优美的，当且仅当集合中任意两个整数 $ x $ 和 $ y $ 满足 $ x $ 能整除 $ y $ 或者 $ y $ 能整除 $ x $。

有 $ t $（$ 1 \le t \le 2 \times 10^4 $）次询问，每次给出整数 $ l, r $（$ 1 \le l \le r \le 10^6 $），每次询问需要给出两个答案：第一个是在集合 $[l, r]$ 中选出整数组成的优美集合的最大大小，第二个是大小最大的优美集合的个数。

**输入输出格式：**
**输入格式：**
第一行包含一个整数 $ t $ —— 测试用例的数量。

每个测试用例包含一行，有两个整数 $ l $ 和 $ r $。

**输出格式：**
对于每个测试用例，输出两个整数：一个是从 $ l $ 到 $ r $ 的整数组成的优美集合的最大可能大小，另一个是大小最大的优美集合的个数。由于第二个数可能非常大，请将其对 $ 998244353 $ 取模后输出。

**输入输出样例：**
**输入样例 #1：**
```
4
3 11
13 37
1 22
4 100
```
**输出样例 #1：**
```
2 4
2 6
5 1
5 7
```**最大集合** **题目大意：** 定义一个正整数集合 $ S $ 是优美的，当且仅当集合中任意两个整数 $ x $ 和 $ y $ 满足 $ x $ 能整除 $ y $ 或者 $ y $ 能整除 $ x $。 有 $ t $（$ 1 \le t \le 2 \times 10^4 $）次询问，每次给出整数 $ l, r $（$ 1 \le l \le r \le 10^6 $），每次询问需要给出两个答案：第一个是在集合 $[l, r]$ 中选出整数组成的优美集合的最大大小，第二个是大小最大的优美集合的个数。 **输入输出格式：** **输入格式：** 第一行包含一个整数 $ t $ —— 测试用例的数量。 每个测试用例包含一行，有两个整数 $ l $ 和 $ r $。 **输出格式：** 对于每个测试用例，输出两个整数：一个是从 $ l $ 到 $ r $ 的整数组成的优美集合的最大可能大小，另一个是大小最大的优美集合的个数。由于第二个数可能非常大，请将其对 $ 998244353 $ 取模后输出。 **输入输出样例：** **输入样例 #1：** ``` 4 3 11 13 37 1 22 4 100 ``` **输出样例 #1：** ``` 2 4 2 6 5 1 5 7 ```