You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

斐波拉契新数列

题目背景

为了保证校赛的公平公正，社长决定在构建题目的时候既要让大多数同学都有参与感，也要设立难题，让顶尖的选手有挑战性。于是便开始了设立题目的过程。

题目描述

为了保证题目的难度，你于是乎按照斐波拉契数列的规则进行造题。

回顾斐波拉契数列，它是这样的一个递增数列:1 1 2 3它的第i项是第i-1项与第i-2项的和。但是这样去设置题目太过于麻烦，并且递增地调控题目不好把控难度。

于是乎你定义了一个斐波拉契新数列，即如下形式建立：

1. 初始化：$a_1$=x, $a_2=y$
2. 并且定义$a_i= @( a_{i-1}+a_{i-2})$

其中 $@(x)$表示对$x$取各数位和直到$x<=9$，如$@(12)=1+2=3$ , $@(99)=@(9+9)=@(18)=@(1+8)=9$

现在社长随机给出了$t$组$x$和$y$，要你求第$k$项的值是多少。

输入格式

第一行，一个整数$t$表示一共有$t$组询问 第$2$至第$t+1$行，给出三个整数$x$、$y$、$k$。表示斐波拉契新数列的初始条件与询问的位置。

输出格式

共$t$行，每行表示每次询问的结果。

样例

输入

5
1 1 9
2 3 7
5 6 4
1 1 1
3 5 4

输出

7
7
8
1
4

数据范围

$1<=t<=10^6$ $1<=x,y<=10^6$ $1<=k<=10^9$