QSC dream of becoming a mathematician, he believes that everything in this world has a mathematical law.

 Through unremitting efforts, one day he finally found the QSC sequence, it is a very magical sequence, can be calculated by a series of calculations to predict the results of a course of a semester of a student.

 This sequence is such like that, first of all, . Then the definition of the QSC sequence is . If we know the birthday of the student is n, the year at the beginning of the semester is y, the course number x and the course total score s, then the forecast mark is .

 QSC sequence published caused a sensation, after a number of students to find out the results of the prediction is very accurate, the shortcoming is the complex calculation. As clever as you are, can you write a program to predict the mark?

First line is an integer T(1≤T≤1000).

The next T lines were given n, y, x, s, respectively.

n、x is 8 bits decimal integer, for example, 00001234.

y is 4 bits decimal integer, for example, 1234.

n、x、y are not negetive.

For each test case the output is only one integer number ans in a line.

数学家QSC

（时间：1s，空间：128Mb）

 QSC梦想成为数学家，他相信世间的一切都有数学规律。

 经过不懈的努力，有一天他终于发现了QSC数列，那是一个很牛逼的数列，可以通过一系列计算预测某人某学期某门课的成绩。

 这个数列是这样的，首先有，那么定义QSC数列，若已知某人的生日n，学期开始时的年份y，课程编号x和课程总分s，则预测成绩为。

 QSC数列公布后引起了轰动，经多位同学亲身试验后发现预测结果十分精确，缺点是计算比较复杂，聪明的你能编写一个程序来预测成绩吗？

Input

第一行一个整数T，表示T(1≤T≤1000)组数据。

接下来T行每行分别给出n，y，x，s。

n、x为8位整数允许有前导零

y为4位整数允许有前导零

Output

对于每组数据，输出成绩，一组数据一行。

样例输入

2

20160830 2016 12345678 666

20101010 2014 03030303 333

样例输出

1

317