Sherlock met Moriarty for a final battle of wits. He gave him a regular n sided convex polygon. In addition to it, he gave him certain diagonals to form regions on the polygon. It was guaranteed that the diagonals did not intersect in interior points.

He took each of the region and calculated its importance value. Importance value for a region formed by vertices a₁, a₂, ... , a_x of the polygon will be given by 2^a₁ + 2^a₂ + ... + 2^a_x. Then, he sorted these regions on the basis of their importance value in ascending order. After that he assigned each region an index from 1 to k, where k is the number of regions, and index of region is its position in the sorted array calculated above.

He wants Moriarty to color the regions using not more than 20 colors, such that two regions have same color only if all the simple paths between these two regions have at least one region with color value less than the color value assigned to these regions. Simple path between two regions f and h is a sequence of regions r₁, r₂, ... r_t such that r₁ = f, r_t = h, for each 1 ≤ i < t regions r_i and r_i + 1 share an edge, and r_i = r_j if and only if i = j.

Moriarty couldn't answer and asks Sherlock to solve it himself. Help Sherlock in doing so.