该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $a_1,a_2$ 和 $n$，规定 $a_i=a_{i-1}+a_{i-2}$（$i\ge 3$），求 $a_n$ 对 $998244353$ 取模后的结果。

本题多测，在一个测试点内，你需要解决 $T$ 组数据。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行三个整数表示 $a_1,a_2,n$。

输出格式

共 $T$ 行，对于每组数据，输出一行一个整数表示 $a_n$ 对 $998244353$ 取模后的值。

样例数据

1
1 2 5

8

1
2 8 10

314

2
3 5 7
14 58 79

55
479708538

3
4 4 4
5 5 5
2 2 2

12
25
2

样例解释

对于样例 $1$，$a_1=1,a_2=2$，所以 $a_3=a_{3-1}+a_{3-2}=1+2=3$，$a_4=a_3+a_2=5$，$a_5=5+3=8$。

对于样例 $4$ 的第三组数据，$a_2$ 为给定值 $2$，可以直接输出。

数据范围

对于 $30\%$ 的数据，保证 $T=1$，$a_1,a_2<20$，$n\le 100$。

对于 $60\%$ 的数据，保证 $T\le 100$，$a_1,a_2\le 1000$，$n\le 10^4$。

对于所有数据，保证 $T\le 1.2\times 10^5$，$0\le a_1,a_2\le 2\times 10^6$，$1\le n\le 2\times 10^6$。