Ailin recently learned linear recurrences, but apparently not the right way. She can not solve a problem proposed by her father ... Can you help her? She has the following system of recurrences: An = Bn = Cn = 4∗An−1 − 3∗Bn−1 − 3∗Cn−1 5∗An−1 − 4∗Bn−1 − 4∗Cn−1 Bn−1 − An−1 And she needs to calculate the value of S(n) defined as follows: { The entry contains a number T, the number of test cases (1 ≤ T ≤ 5∗105). Each of the following T lines contain an integer n (1 ≤ n ≤ 9∗1018) and the values of A0, B0, C0 (0 ≤ A0, B0, C0 ≤ 9). Output The output will contain T lines, each with the value of S(n) defined above. Since the sum can be very large, print only the last digit. More formally, in each case print a no negative number, the result modulo 10. Remember that if a mod M < 0 then you should add M to the result, so the answer is no negative. More formally you can use: ((a mod M) + M) mod M Sample Input 5 1123 4123 7123 100001 1 2 1 900000 1 2 9 Sample Output 5 1 7 8 0 0 if n = 0 S(n − 1) + An + Bn + Cn if n ≥ 1 S(n) = She knows that there is a method to calculate this result quickly, but she is something lazy and asks you for help to find the answers. Input