gcd 与 lcm

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定两个正整数 $x,y$，求有多少个不同的长度为 $n$ 的正整数序列 $(a_1,a_2,\ldots,a_n)$，满足所有元素的最大公约数为 $x$，且所有元素的最小公倍数为 $y$。

如果两个序列至少有一个位置上的元素不同，则认为它们是不同的序列。

答案可能很大，请输出其对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $Q$，表示询问次数。

接下来 $Q$ 行，每行包含三个整数 $x,y,n$，表示一组询问。保证每组询问至少存在一个满足条件的序列。

输出格式

输出 $Q$ 行，每行一个整数，依次表示每组询问的答案。

样例输入 1

3
3 6 2
12 144 3
233 251640 10

样例输出 1

2
72
905954656

数据范围

对于所有数据，$1\le Q\le100$，$2\le n\le10^5$，$1\le x,y\le10^9$。