問題文

赤色のボタンと青色のボタンがあります。MMA くんは、このボタンを押して遊ぶことにしました。

MMA くんはスコアと呼ばれる数を持っており、最初の時点ではスコアは $0$ です。

赤色のボタンを押すと、MMA くんのスコアが $A$ だけ上昇します。

青色のボタンを押すと、MMA くんのスコアが $B$ 倍になります。

高々 $K$ 回までボタンを押すことができるとき、MMA くんが達成できる最大のスコアを求めてください。

ただし、答えは非常に大きくなることがあるため $998244353$ で割ったあまりを出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• $1 \leq T \leq 2 \times 10^{5}$
• $|A|, |B| \leq 10^{9}$
• $1 \leq K \leq 10^{9}$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは以下の形式で与えられる。

$A$ $B$ $K$

出力

$T$ 行出力せよ。

$i$ 行目には、$i$ 番目のテストケースに対する答えを $998244353$ で割ったあまりを出力せよ。

サンプル

2
4 2 3
23 57 38

16
343383691