So, here you are finally competing for the title of the champion of C3W. But before you go any further we've got something for you. It's not at all difficult if you're meant to be the guy who takes it all.

Given are some numbers against which a number has been calculated as it's output. identify the logic behind it and move further.

2 => 1
13 => 3
71 => 4
55 => 5
111 => 6

Input format:
An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=10⁹.

Output format:
For each integer given as input, output the required answer as a single integer.