Number Baseball

Interview

Time limit1sMemory limit128 MB

Summary

Given N guesses with strike and ball counts in a number-baseball game, count how many three-distinct-digit numbers are consistent with all clues.

Level: Easy3 of 10
Topics: Brute force, Simulation
Solved: No attempts yet

Problem

Minhyuk and Youngsu are playing number baseball. Youngsu thinks of one three-digit number made from three distinct digits from 1 through 9. Minhyuk asks about three-digit numbers that satisfy the same condition, and Youngsu answers with the number of strikes and balls according to these rules.

A digit that appears in the same position counts as one strike.
A digit that appears in the number but in a different position counts as one ball.

Youngsu answered every question honestly, and the given answers do not contradict each other. Given all questions and answers so far, find how many numbers Youngsu could be thinking of.

Input

The first line contains the number of questions, N. N is between 1 and 100, inclusive.

Each of the next N lines contains three values separated by spaces: the three-digit number Minhyuk asked about, the number of strikes in Youngsu's answer, and the number of balls in Youngsu's answer. Each asked number is made from three distinct digits from 1 through 9.

Output

Print the number of three-digit numbers Youngsu could be thinking of.

Examples1

Example 1
Input
```
4
123 1 1
356 1 0
327 2 0
489 0 1
```
Expected output
```
2
```