Terminal Cities

There are N cities. Some pairs of cities are connected by bidirectional roads, and in the initial road network every city can reach every other city.

To reduce maintenance cost, some roads may be closed. As many roads as possible should be removed, but the remaining roads must still allow every city to reach every other city.

In the remaining road network, a city is called a terminal city if it is directly connected to exactly one other city. Using only roads from the given network while preserving connectivity, find the maximum possible number of terminal cities.

The first line contains the number of cities N. N is at most 15.

The next N lines contain the adjacency matrix. If the j-th character of a row is 1, there is a road between that row's city and city j; if it is 0, there is no such road.

Print the maximum possible number of terminal cities.