#P2478. 假如再也碰不到你,祝你早安、午安、晚安

假如再也碰不到你,祝你早安、午安、晚安


 

众所周知,小东是个很怂的人。在元旦的时候小东() 难得鼓起勇气去找小鹏(),但是在途中遇见了大魔王王小帅,小东凭借自己的高超的高数水平通过了王小帅的考验。在抵达小鹏的学校,小东却没有勇气喊小鹏出来,在纠结了好一会,小东终于鼓起勇气要喊小鹏。就在此时

大魔王王小帅又出现了。以下是大魔王和小东的对话:

大魔王(王小帅):【邪恶笑】,如果你想见到那个女生必须通过我设立的考验。

小东:还来,但是天太冷,不想打字,你知道我想说什么。

大魔王(王小帅):【邪恶笑】没想到你竟然有勇气接受我的考验。请听题:

假定你在一个叫“京友亭”的亭子,小鹏在宿舍楼向你这走来。小鹏的宿舍楼离京友亭特别远。同时小鹏有个不开心值k,刚开始k0。小鹏的宿舍到京友亭是一条长达m米的直线。这m米的直线上平均分配着m块长达1米的板砖。因为小鹏的学校的风很大,假定每块板砖上的风速是f[i].那么f[i] = f[i-1] + f[i-2]。前两块的板砖的风速直接给你。小鹏每走上一块板砖,不开心值就会加上这块板砖的风速。现在你要求出小鹏到达京友亭的不开心值

小东:[悲痛欲绝] 该死,我大学没好好学数学高数,不然我一定能做出来。为了能见到小鹏,小东决定向同样高数没学好的聪明绝顶的你求助。




Input


首先输入一个整数T(1<=T<=10)代表T组数据 接下来一行输入一个整数m(3<=m <=50)代表小鹏的宿舍到京友亭一共有多少板砖;

接下来输入a,b代表前两块板砖的风速。1<= a,b <= 1000000;



Output

对于每组数据输出一个数代表小鹏达到京友亭的不开心值。

Sample Input

2
5
3 5
6
3 4

Sample Output

50
72

HINT

Source