Tuenti Challenge 10

Challenge 5 - Tuentistic Numbers

A Tuentistic number is any number that, when written in English, contains the word “twenty” (for example, 20, 21 or 120000). Since at Tuenti we love Tuentistic numbers, we like to represent any non-Tuentistic number as a sum of positive Tuentistic numbers in order to increase their Tuentisticness (this is called a Tuentistic sum). For example, the non-Tuentistic number 50 can be represented as the Tuentistic sum 25 + 25. The Tuentistic numbers thenselves count as Tuentistic sums too.

Given a positive number, we want to know the maximum number of elements of its Tuentistic sums.

Input

The first line contains the number of cases C. Then, C lines follow, each with a number N.

Output

For each case, output 'Case #X: M', where X is the case number (the first case has number 1) and M is the maximum number of elements in a Tuentistic sum of N. If it is not possible to represent N as any Tuentistic sum, write 'Case #X: IMPOSSIBLE' instead.

Limits

  • 1 ≤ C ≤ 500
  • 1 ≤ N ≤ 262

Sample Input

3
20
80
35

Sample Output

Case #1: 1
Case #2: 4
Case #3: IMPOSSIBLE

In the first case, the number 20 has only one Tuentistic sum which contains itself, so the answer is 1.
In the second case, 80 can be represented as a sum of 4 Tuentistic numbers (20+20+20+20).
In the third case, it's impossible to sum 35 with only Tuentistic numbers.

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want. Be careful with extra whitespace. The output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you have to solve the test phase before you can submit your code. You must provide the source code used to solve the challenge and you can only make one submission. After your solution is submitted, you won't be able to modify it to fix issues or make it faster.

If you have any doubts, please see the info section.

Problem stats

Completion time: min: 0:05:22 h
10th percentile: 0:19:19 h
90th percentile: 19:38:29 h
max: 97:33:04 h
Test phase time: 10th percentile: 0:17:45 h
90th percentile: 18:54:23 h
Submit phase time: 10th percentile: 0:00:42 h
90th percentile: 0:08:09 h
# of completions:284