Triangle

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Mr. Frog has n sticks, whose lengths are 1,2, 3$\cdots $n respectively. Wallice is a bad man, so he does not want Mr. Frog to form a triangle with three of the sticks here. He decides to steal some sticks! Output the minimal number of sticks he should steal so that Mr. Frog cannot form a triangle with
any three of the remaining sticks.

Input

The first line contains only one integer T ($T\leq 20$), which indicates the number of test cases.

For each test case, there is only one line describing the given integer n ($1\leq n \leq 20$).

Output

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1), y is the minimal number of sticks Wallice should steal.

Sample Input

3 4 5 6

Sample Output

Case #1: 1 Case #2: 1 Case #3: 2

Hint

wange2014

Source

2016中国大学生程序设计竞赛(长春)-重现赛

提交代码