给定两个数 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 行，每行包含一个整数，依次表示每个询问的答案。

对于 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。