ICANDIES - Candies

Sava is a student of class X. She has two little sisters Sara and Sami. Sara is only 3 years old and Sami is a girl of 5 years. At her birthday Sava bought N candies and wants to divide them between her two sisters Sara and Sami. But as Sara is 3 years old she wants such amount of candies that is perfectly divisible by 3. Sami also wants the amount of her candies to be perfectly divisible by 5 and only this way both of them are happy otherwise they become unhappy.

So, Sava wants to make both of them happy. Now for some value of N Sava can divide the candies in various ratio that will make her sisters happy. But as Sara is the youngest one she wants to give the maximum number of candies she can. As Sava is not good enough in math, she wants your help.

Input

Input starts with an integer T (1≤T≤50), denoting the number of test cases. Each of the test cases consists an integer N (1≤N≤106), the number of candies Sava bought.

Output

For each case print "Case X: " where X (1≤X≤T) is the case number. And then, if it is possible to divide the candies making both of them happy print the maximum number of candies you can give to Sara. And if it is not possible to make both of them happy then print '-1' (without the quotes).

Example

Input:
3
8
9
20

Output:
Case 1: 3
Case 2: -1
Case 3: 15

Added by:imranziad
Date:2015-10-07
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB Beginners Team Formation Contest (Round 5) Onsite

hide comments
2016-02-28 07:12:58
Easy Problem! but forgetting a " " (space) gave me a WA

Last edit: 2016-02-28 07:13:55
2016-01-10 09:46:53
extra "\n" after each output ..... costed 1WA

Last edit: 2016-01-10 09:47:12
2016-01-04 08:16:55
this problem is very easy ,, why are there only few submissions for this?
2015-12-19 11:08:06 gomathi ganesan
Those who are getting WA check the test case 25.
Answer is 15 and not -1

Last edit: 2015-12-30 10:08:58
2015-10-18 09:17:21
is there a blank line after each input?
2015-10-18 09:07:13 kataria
nice problem !!!
2015-10-13 20:29:17
@imranziad Is there any blank line after each output?

PS: There aint any blank line.

Last edit: 2015-10-14 16:56:06
2015-10-12 12:16:16
Does anyone have additional test cases? My solution works fine with all numbers up to 30, yet I get wrong answer.
Solution ID: 15348930

Last edit: 2015-10-12 12:17:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.