Sudoku Sum

Solve each Sudoku puzzle in the input and report the sum of the 3-digit numbers formed by the top-left corner of each solution.

A valid Sudoku solution contains the digits 1–9 in each row, each column, and each 3×3 box, with no repeats. Every puzzle in the input has a unique solution.

Input

Line 1: an integer K — the number of puzzles. For each puzzle: 9 lines of 9 digits with no spaces, where 0 represents a blank cell. A blank line separates consecutive puzzles.

Output

A single integer: the sum across all K puzzles of solved[0][0]*100 + solved[0][1]*10 + solved[0][2].

Example

Input:

1
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300

Output:

483

The solved puzzle has 4, 8, 3 as its top-left three digits.

Notes

• A standard backtracking search starting from the first empty cell will solve typical puzzles.

Scoring

Your solution is evaluated against 10 test cases worth 10 points each (100 total).