给定两个数 x, y ，求有多少种不同的长度为 n 的序列 (a1, a2, · · · , an)，其所有元素的最大公约数为 x 且最小公倍数为 y 。
两个序列 (a1, a2, · · · , an) 与 (b1, b2, · · · , bn) 不同，是指存在至少一个位置 i满足 ai , bi 。
由于答案可能很大，请输出答案对 998244353 取模后的结果。
输入的第一行包含一个整数 Q 表示询问次数。
接下来 Q 行，每行包含三个整数 x,y,n 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。
输出 Q 行，每行包含一个整数，依次表示每个询问的答案。
3 3 6 2 12 144 3 233 251640 10
2 72 905954656
【评测用例规模与约定】
对于 40% 的评测用例，n ≤ 30 ；
对于 70% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ Q ≤ 100 ，2 ≤ n ≤ 105 ，1 ≤ x, y ≤ 109 。