URI 1629 - UnzipFACE

In 2013, FACE Fair compressed their visitors data with a free zipper. Unfortunately, this tool started to be paid and you were asked to create an algorithm to unzip the data. The data are compressed in a decimal format, and in order to run the unzipped you are asked to find each compressed line checksum. FACE organization got a documentation of how the process worked, but some information on how to get the digits are not clear, the document only provides some examples, as follow:

Compacted line composed by 54782 when unpacked would result in the binary string 00000111100000001111111100, with it, the digit value would be 8.
Compacted line composed by 045 when unpacked would result in the binary string 111100000, with it, the digit value would be 9.

Input

The input contains several test cases. A test case first line contains an integer N (1 ≤ N ≤ 25), representing the visitors data number from that file, wherein, each line represents a visitor. The following N lines consist of K digits (1 ≤ K ≤ 10³) without space representing the compacted line. The stop is given by N equals 0.

Output

For each compacted line you must display the uncompressed checksum digit.

Sample Input	Sample Output
5 7 54782 0158309 12345678910 987654321 0	7 8 17 10 9