Tic-Tac-Toe-Nim

Problem Description

Alice and Bob are playing a new game that is a mixture of tic-tac-toe and nim. There are $9$ piles of stones forming a $3*3$ grid. Players take turns to remove the stones: in each turn, the player choose a remaining pile and remove a positive number of stones from it. Alice goes first. The first player to remove a pile so that a new empty row or column is formed wins. Notice that player does NOT have to be the one to remove all three piles to win, and diagonals does NOT count as a win. However, to speed up the game, both players have decided they will always remove the whole pile they choose in their respective first turn, instead of removing only part of the pile. Now Alice wants to know how many different moves can she choose in the first turn so that she can still ensure her victory.

Input

The first line contains one integer $T$ ($1 \leq T \leq 500000$), the number of test cases. For each test case, there are $3$ lines, each contains $3$ integers $a_{ij}$ ($1 \leq a_{ij} \leq 10^9$), denoting the number of stones in each pile.

Output

For each test case, output one integer denoting the answer. Output $0$ when Alice can not win in the situation.

Sample Input

2
1 1 1
1 1 1
1 1 1
1 2 3
4 5 6
7 8 9

Sample Output

9
7

Source

2020 Multi-University Training Contest 10