Traditional BINGO

Interview

Time limit1sMemory limit128 MB

Summary

For each card, find how many announced numbers are needed before some row, column, or diagonal of five spaces is fully marked, with the center free.

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

Problem

Traditional BINGO is played in person in a large hall. Players gather, pay an entry fee, and then the games begin. A night of BINGO consists of many games played continuously, one after another.

A single BINGO game works like this. Each player holds one or more BINGO cards (a player may play any number of cards). Every card has 5 rows and 5 columns, giving 25 spaces.

The columns are labeled, from left to right, with the letters B, I, N, G, and O. With one exception — the center space is "free" — every space holds a number, assigned as follows:

Each space in the B column holds a number from 1 to 15.
Each space in the I column holds a number from 16 to 30.
Each space in the N column holds a number from 31 to 45.
Each space in the G column holds a number from 46 to 60.
Each space in the O column holds a number from 61 to 75.

A number may appear at most once on a single card.

A sample BINGO card:

B	I	N	G	O
10	17	39	49	64
12	21	36	55	62
14	25	FREE SPACE	52	70
7	19	32	56	68
5	24	34	54	71

The number of distinct BINGO cards is very large:

// the B, I, G, and O columns * the N column
(15 * 14 * 13 * 12 * 11) ^ 4 * (15 * 14 * 13 * 12)

Interesting to a statistician, perhaps, but this count has nothing to do with a player's chances of winning.

There are 75 possible BINGO numbers in total:

B1, B2, B3, ... B15, I16, I17, ... I30, N31, N32, ... O74, O75

Each number is painted on a ball inside a large rotating bin. The announcer spins the bin, draws a ball, and announces its number. Every player checks all of their cards; if the number appears on a card, that space is marked. The center FREE SPACE may be marked at any time (treat it as always marked).

When a player has a BINGO — five marked spaces in a single row, column, or diagonal — that player calls out "BINGO". The card is verified, and if it is a genuine winner the game stops. Every BINGO game runs until someone wins.

Input

The first line contains $n$ , the number of BINGO games to analyze. Then $n$ game descriptions follow.

Each game description begins with a card, given as five lines (one line per row). Rows 1, 2, 4, and 5 each list 5 numbers; row 3 lists only 4 numbers, because its center space is the free space.

After the card, one or more lines list some ordering of all 75 BINGO numbers — the exact sequence in which they are announced. Every value is an integer from 1 to 75 (the single-letter column prefix is redundant and is omitted).

Assume the card holder is the only player and plays only this one card, so the game ends the moment this card first makes a BINGO.

Output

For each game, print one line:

BINGO after N numbers announced

where $N$ is the number of announced numbers at the moment the card first achieves a BINGO — a full row, column, or diagonal, with the free center space always counting as marked.

Hint

Chances of Winning

Every BINGO game has a winning card, so a player's chance of winning depends on how many cards are in the game and how many of them that player holds. For example, a player holding 12 cards in a game with 1200 cards has a 1 in 100 chance of winning.

Examples1

Example 1

Input

1
10 17 39 49 64
12 21 36 55 62
14 25 52 70
7 19 32 56 68
5 24 34 54 71
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75

Expected output

BINGO after 14 numbers announced