Bạn có ~34~ đồng xu có giá trị như sau:

• ~xu(1)~ có giá trị ~2~
• ~xu(2)~ có giá trị ~3~
• ~xu(3)~ có giá trị ~5~
• ~xu(n)~ có giá trị ~\left(xu(n-1) + xu(n-2) + xu(n-3)\right)~

Bạn hãy dùng nhiều đồng xu nhất để mua một món hàng có giá là ~X~.

Input

Dòng đầu tiên là số test (không quá ~1000~). Mỗi dòng tiếp theo chứa một số nguyên ~X \left(1 \leq X \leq 2\,000\,000\,000\right)~.

Output

Với mỗi test, in ra "Case #" + số hiệu test + ": " + số lượng lớn nhất đồng xu cần dùng. Nếu không có cách nào để đạt giá trị ~X~ thì in ra ~-1~.

Sample Input

4
1
5
8
9

Sample Output

Case #1: -1
Case #2: 2
Case #3: 2
Case #4: -1