← 返回题目列表

Codeforces · 1796/C

C. 最大设置

中文机器翻译题面 查看原题

一组正整数 $$$S$$$ 被称为美丽的,如果对于该集合中的每两个整数 $$$x$$$ 和 $$$y$$$,$$$x$$$ 整除 $$$y$$$ 或 $$$y$$$ 整除 $$$x$$$(或两者)。

给你两个整数 $$$l$$$ 和 $$$r$$$。考虑所有由不小于 $$$l$$$ 且不大于 $$$r$$$ 的整数组成的美丽集合。您必须打印两个数字:

- 一个漂亮集合的最大可能大小,其中所有元素都从 $$$l$$$ 到 $$$r$$$;
- 由 $$$l$$$ 到 $$$r$$$ 之间的整数组成的美丽集合的数量,具有最大可能的大小。

由于第二个数字可能非常大,因此打印它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le 10^6$$$)。

输出

对于每个测试用例,打印两个整数 - 由从 $$$l$$$ 到 $$$r$$$ 的整数组成的漂亮集合的最大可能大小,以及具有最大可能大小的此类集合的数量。由于第二个数字可能非常大,因此打印它对 $$$998244353$$$ 取模。

示例

输入 #1

4
3 11
13 37
1 22
4 100

输出 #1

2 4
2 6
5 1
5 7

注意

在第一个测试用例中,包含从 $$$3$$$ 到 $$$11$$$ 整数的漂亮集合的最大可能大小是 $$$2$$$。有 $$$4$$$ 这样的集合具有最大可能的大小:

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