給定兩個數(shù) x, y ，求有多少種不同的長度為 n 的序列 (a1, a2, · · · , an)，其所有元素的最大公約數(shù)為 x 且最小公倍數(shù)為 y 。

兩個序列 (a1, a2, · · · , an) 與 (b1, b2, · · · , bn) 不同，是指存在至少一個位置 i滿足 ai , bi 。

由于答案可能很大，請輸出答案對 998244353 取模后的結(jié)果。

輸入的第一行包含一個整數(shù) Q 表示詢問次數(shù)。

接下來 Q 行，每行包含三個整數(shù) x,y,n 表示一組詢問，相鄰整數(shù)之間使用一個空格分隔。對于每個詢問，保證至少存在一個滿足條件的序列。

輸出 Q 行，每行包含一個整數(shù)，依次表示每個詢問的答案。

3
3 6 2
12 144 3
233 251640 10

2
72
905954656

【評測用例規(guī)模與約定】

對于 40% 的評測用例，n ≤ 30 ；

對于 70% 的評測用例，n ≤ 5000 ；

對于所有評測用例，1 ≤ Q ≤ 100 ，2 ≤ n ≤ 10⁵ ，1 ≤ x, y ≤ 10⁹ 。