Chain Code

In a black-and-white (bi-level) image, a set of connected black pixels can be treated as a foreground object, while the white pixels form the background. A connected set of black pixels can be described completely by listing, in counterclockwise order, the positions of the pixels on its boundary, starting from an arbitrary boundary pixel. Instead of storing positions, we store only the direction from each boundary pixel to the next one in the list. This sequence of directions is called the chain code of the object; it describes the object's shape exactly while being independent of the object's position.\n\nThere are 8 possible directions from a pixel to an adjacent pixel. The numbering is a convention: direction 0 points to the right, direction 2 points straight up, direction 1 is the 45° direction that bisects 0 and 2, and the rest continue counterclockwise. The full convention is:\n\n\n3 2 1\n4 . 0\n5 6 7\n\n\nwhere . marks the current pixel; that is, 0 = right, 1 = up-right, 2 = up, 3 = up-left, 4 = left, 5 = down-left, 6 = down, 7 = down-right.\n\nAssuming one pixel at every integer coordinate, two black pixels are adjacent when the squared distance between them is at most 2 (that is, they touch orthogonally or diagonally). Two pixels are connected if a path of pairwise-adjacent pixels links them, and a connected region is a set of black pixels that are all mutually connected. A boundary pixel of a region is a pixel of the region that has at least one of its four orthogonal (up/down/left/right) neighbors not black. You may assume the region has no holes, so it has exactly one boundary.\n\nA chain code may start at any boundary pixel. From the current pixel it repeatedly finds the next boundary pixel in the counterclockwise direction, appends that direction (0–7) to the output, and moves on; when it returns to the starting pixel the chain code is complete. Shape measures such as perimeter and area (the number of pixels in the region) can be computed directly from the chain code alone. Given only the chain code, compute the area of the connected region.

The input is a collection of chain codes, one per line. Each chain code consists of the digits 0–7 and contains at most 1,000,000 characters. Every chain code describes a valid region whose boundary does not intersect itself. Input ends at end of file.

For each chain code in the input, print the area of its region — the number of pixels the region contains — on its own line.

The boundary described by a chain code is a closed walk over pixel centers: directions 0/2/4/6 move one step orthogonally and directions 1/3/5/7 move one step diagonally. Because the region has no holes, this walk is a single simple closed curve, and the number of pixels it encloses (boundary pixels included) can be recovered from the walk alone, without reconstructing the whole image.