Kick Start offers coders around the world the chance to develop and hone their programming skills through online-hosted competition rounds.
Supervin has a unique calculator. This calculator only has a display, a plus button, and a minus button. Currently, the integer N is displayed on the calculator display.
Pressing the plus button increases the current number displayed on the calculator display by 1. Similarly, pressing the minus button decreases the current number displayed on the calculator display by 1. The calculator does not display any leading zeros. For example, if 100 is displayed on the calculator display, pressing the minus button once will cause the calculator to display 99.
Supervin does not like odd digits, because he thinks they are "odd". Therefore, he wants to display an integer with only even digits in its decimal representation, using only the calculator buttons. Since the calculator is a bit old and the buttons are hard to press, he wants to use a minimal number of button presses.
Please help Supervin to determine the minimum number of button presses to make the calculator display an integer with no odd digits.
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the integer initially displayed on Supervin's calculator.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of button presses, as described above.
1 ≤ T ≤ 100. Time limit: 20 seconds per test set. Memory limit: 1GB.
Small dataset (Test set 1 - Visible) 1 ≤ N ≤ 105.
Large dataset (Test set 2 - Hidden) 1 ≤ N ≤ 1016.