题目描述

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

两个序列 $(a_1,a_2,\cdots,a_n)$ 与 $(b_1,b_2,\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\neq b_i$。

由于答案可能很大，请输出答案对 $998\ 244\ 353$ 取模后的结果。

输入格式

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

接下来 $Q$ 行，每行包含三个整数 $x,y,n$ 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。

输出格式

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

3
3 6 2
12 144 3
233 251640 10

2
72
905954656

提示

对于 $40\%$ 的评测用例，$n\le 30$；
对于 $70\%$ 的评测用例，$n\le 5000$；
对于所有评测用例，$1\le Q\le 100$，$2\le n\le 10^5$，$1\le x,y\le 10^9$。