Adel is a student at the 2nd year in faculty of computer and information science. One day he was attending a probability lecture, the lecturer found that students got bored of the content of the topic he was discussing, at the end of the lecture he thought that students will not understand this topic well enough, so he decided to make a challenge. Unfortunately Adel was falling asleep, but he woke up at the end of the lecture, so he didn't know about the challenge. Adel heard from his friends about the challenge, so he asked about it and his friend replied “The lecturer said that he will send a 100 easy problem to our emails about this topic, and the first ten people who will get the full mark will get the full mark in midterm”. After that Adel went to home and studied the topic well, He found out that all problems have the same idea so he wanted to use the speed of computers to compute the results of these problems and to be in the top ten. So he asked you to do this task. The problem is that you have a set of letters L where (0 < L <= 15). You have to know how many ways you can get a L-digit number that satisfies L conditions. This L-digit number does NOT contain zeros.

You have 5 conditions:

• ‘N’ ==> Normal digit.
• ‘P’ ==> Prime digit (1 is not prime.)
• ‘E’ ==> Even digit.
• ‘S’ ==> Perfect Square.
• ‘O’ ==> Odd digit.

For more clarification, let’s take this example. You have a string “NPE”. This string means that you need to know how many 3-digit number that its 1st digit is a Normal digit (0 < N <= 9), its 2nd digit is a Prime number and the last one is an Even digit. You have to tell Adel how many numbers satisfy these conditions. You can repeat the same digit in the same number as you like.

A perfect square is the product of some integer with itself. For example, 9 is a square number, since it can be written as 3 × 3.

Input

The first line is the number of test cases (1 <= T <= 3000.) Each test case include a string that contains only (‘N’, ’P’, ’E’, ’S’, ’O’) and the string has a maximum length of 15 (0 < L <= 15.)

Output

For each test case print "Case_#i:_X" where "i" is the test case number and "X" is result of how many numbers satisfy the Input’s condition, "_" is a space. Each test case should be printed in a separate line.

Example

Input:
3
N
NO
PEPSE

Output:
Case #1: 9
Case #2: 45
Case #3: 768