This problem is a programming version of Problem 97 from projecteuler.net
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form ; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form , have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: .
Now we want to learn how to calculate some last digits of such big numbers. Let's assume we have a lot of numbers and we want to know last 12 digits of these numbers.
Input Format
First line contains one integer T - the number of tests.
T lines follow containing 4 integers (A, B, C and D) each.
Constraints
Output Format
Output exactly one line containing exactly 12 digits - the last 12 digits of the sum of all results. If the sum is less than print corresponding number of leading zeroes then.
Sample Input
1
2 3 4 5
Sample Output
000000000167
Explanation