China is the most populated country in the world and has more than a fifth of the world population. In 1953 the first modern census was taken in the country, re- vealing a population near 600 millions of inhabitants. In the 60s the government started to promote the de- lay of the age of marriage and also family planning policies. In 1972 the first limitations on the number of children per family were stablished; in the cities they were limited to two. The one child policy was implanted in 1979 in order to slow down the popula- tion growth, which by that time had arleady reached 1000 million of inhabitants. This policy combined the use of advertising, social pressure, a benefits program and even economic penalties. However, the ethnic minorities were exempt and in the rural environments, families were allowed to have a second child in case the first-born was a girl. In 2015 the one child policy was abolished and replaced by a two-child policy. A group of chinese demographers are studying genealogical trees of chinese families in which the two child policy stablished in 1972 and recently recovered has been accomplished. In each family they study the generationally complete subfamilies, i.e. those in which all their members have had exactly two children. They want to know which is the generationally complete subfamily with most number of generations. As an example, in the following genealogical tree it is highlighted the generationally complete subfamily with most number of generations, which are two in this case. Input The first line contains the number of proof cases appearing below. Each proof case is a sequence of numbers 0, 1 or 2 indicating the number of children of the family members. First the number of the genealogical tree’s root is shown and then the description of the subfamilies of its children appear, which are described in the same way. The genealogical trees never contain more than 5,000 members.
2/2 Output For each genealogical tree, write a line with the number of generations of the generationally complete subfamily with most number of generations. Sample Input 5 0 200 121010 2201200200 2220210022000120200 Sample Output 0 1 1 2 2