### 问题描述 在遥远的北国小镇，住着一位名叫艾丽丝的小女孩。艾丽丝对数学有着浓厚的兴趣，特别是集合论。在她的眼中，世界就像一个巨大的集合，而圣诞节则是一个集合与集合之间奇妙的交集。 圣诞节前夕，艾丽丝兴奋地装饰着圣诞树，她用各种颜色的彩灯、闪亮的装饰品和精心挑选的礼物将树装饰得五彩斑斓。她将每个礼物看作是一个集合，每个集合都有独特的元素。有的集合是玩具，有的集合是书籍，还有的集合是美食，现在艾丽丝希望你帮助求解以下集合论问题。 给定正整数 $l,r,k$，请你求解有多少个不可重非空正整数集合 $A$，满足： > 1. 集合中所有的数均为 $[l,r]$ 中的正整数。 > 2. 若存在正整数 $x \in A$，那么一定有 $kx \notin A$。 由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。 ### 输入格式 第一行包含一个正整数 $T$，表示数据组数。 之后对于每组数据，输入共一行，包含 $3$ 个正整数 $l,r,k$。 ### 输出格式 对于每组数据输出一行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。 ### 样例输入 ```text 2 1 3 2 114514 1919810 233 ``` ### 样例输出 ```text 5 183010726 ``` ### 评测数据规模 对于所有测评数据，$1 \leq k \leq 10^{18},1 \leq l \leq r \leq 10^{18},1 \leq T \leq 10^4$。