题目描述

火山宝打算造一个 $n$ 位的十进制数字出来。对于 $1$ 到 $n$ 中的每一个 $i$，火山宝可以从 $x_{i,1}, ..., x_{i,k_i}$ 这 $k_i$ 个 $0\sim 9$ 的数字中选择一个作为 $a_i$。在选择结束后，$a_1a_2...a_n$ 形成了一个 $n$ 位的十进制数 —— 这就是火山宝造出来的数。

你需要帮火山宝计算他能造出的数中，有多少个是 $3$ 的倍数。

输入格式

第一行输入一个整数 $n\ (1 ≤ n ≤ 18)$，表示数字的位数。

接下来 $n$ 行，每行第一个整数 $k_i\ (1 ≤ k_i ≤ 10)$，表示第 $i$ 种候选的数字数量。

接着是 $k_i$ 个两两不同的 $0\sim 9$ 范围内的数字 $x_{i,1}, ..., x_{i,k_i}$。输入保证 $0$ 不是第一位的可选项。

输出格式

你需要输出一行一个整数，表示火山宝能造出的数字中，$3$ 的倍数的数量。

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

9

能造出来的 $3$ 的倍数有 $51, 54, 60, 63, 72, 81, 84, 90, 93$。

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

30000