最好的序列（Hard）
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

注意区分本题的 Easy 和 Hard 版本，两个版本问的问题不是一样的！！
称满足如下条件的序列 a 是 “好序列”：
  • \forall i\in[1,n]，1\leq a_i\leq X。
  • LCM(a_1,a_2,...,a_n)\leq Y。

在所有 “好序列” 中，序列中未出现的最小正整数最大的序列称为 "最好的序列"。

请问有多少种不同的 “最好的序列” ，答案对 998244353 取模。

输入描述:

本题有多组测试数据。

第一行输入一个整数 T(1\leq T\leq 2\times 10^4)，表示数据组数。

接下来 T 行，每行输入 3 个整数 n,X,Y(1\leq n,X,Y\leq 10^{14})。

输出描述:

对于每组测试数据，输出有多少种不同的 “最好的序列”。
示例1

输入

复制 
4
2 4 6
4 10 29
123 456 789
20 20 301027

输出

复制 
2
24
462553434
511292827

说明

第一组样例：答案序列可以为 \{1,2\} 或者 \{2,1\}，其最小未出现的正整数都是 3，这是所有最好的序列中最小未出现的正整数最大的，且 LCM(1,2)=2\leq 6。