New Stone Game

Problem Description

Alice and Bob are playing a tic-tac-toe-like game on $9$ piles of stones arranged in a $3 \times 3$ grid. Players take turns removing stones. In each round, a player chooses one pile and removes a positive number of stones from it. Alice moves first. The first player to complete an empty row or an empty column wins. (A row or column does not need to be emptied entirely by the same player; a diagonal empty line does not count as a win.)

Special rule: On a player's very first stone removal, they must remove the entire chosen pile.

If both players play optimally, Alice wants to know which piles she can choose for her first move to guarantee that she wins. Output the number of such winning first moves.

Input Format

The first line contains an integer $T$.

The following $T \times 3$ lines each contain three integers, describing one $3 \times 3$ grid per test case.

Output Format

Output $T$ lines, each containing a single integer.

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

Constraints

All data satisfy $1 \le T \le 5 \times 10^5$ and $1 \le$ (stones in each pile) $\le 10^9$.