一组正整数 $$$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 \}$$$.