_{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**