The Bright Beacen managing commity tasked a young man by the name of Lamin to organise the shoe racks during the evenings. in the previous years, some people had lost their shoes because they forgot which rack they placed them on. Young brother Lamin was asked to give everyone a ticket with the rack number as they walk into the mosque.
The racks are an array of 9x135 which means that there is enough space for 1215 pairs of shoes. This is fine for a regular evening but during Ramadan, this is not enough space. Therefore plastic bags are given out so that people can keep shoes with them if there is no space on the racks.

They didn't know that Lamin was a sudoku enthusiast and the racks of 9x135 just happen to create 15 perfect sudoku style grids of 9x9.

Lamin has been cheekily arranging shoes in racks from shoe sizes 1 to 9. But only if they would perfectly fit in a sudoku style grid where the rules are as such...

The rules

• every horizontal line can only have numbers 1 to 9 once
• every vertical line can only have numbers 1 to 9 once
• every grid of 9x9 is made up of 9 smaller grids of 3x3. Each 3x3 grid can only have the numbers 1 to 9 once.

If anyone has a shoe size larger than 9, he has given them a carrier bag and told them there is no space on the racks for their shoes 😬.

About your input file

• He has supplied a file with the 15 9x9 grids that represent the racks.
• on the file, each line represents one 9x9 grid in a 2D array.
• a 0 represents a blank space in the grid/rack

He would like to know how many spaces there are left for all the different sizes of shoes.

A space is valid for a shoe size if placing that number does not violate Sudoku rules for that grid.

Your Task

Work out how many spaces there are for each shoe size.

Your answer must be in the format:

1x2_2x5_3x2_4x0_5x2_6x7_7x1_8x0_9x12

Meaning:

• Shoe size 1 can fit in 2 spaces
• Shoe size 2 can fit in 5 spaces etc.
• There must be no spaces in your output string.