Pool Balls

Time limit1sMemory limit128 MB

Summary

Count squares v with a < v < b whose predecessor v-1 is a triangular number, over several test cases.

Level: Medium5 of 10
Topics: Math, Number theory, Binary search, Brute force
Solved: No attempts yet

Problem

Sunyoung borrowed a pool table from Sanggeun, who also lent her a 4x4 tray that holds 16 balls. One ball is the white cue ball and the other 15 are numbered 1 through 15. Before a game of pool the numbered balls are packed into a triangle with no gaps: the 15 numbered balls form a triangle, and all 16 balls together fill the 4x4 tray.

Sunyoung invents a new game played with the cue ball and x numbered balls. To be playable, the x numbered balls must pack exactly into a triangle (using every ball, with no empty position), and all x + 1 balls (the numbered balls plus the cue ball) must fill an m x m square tray exactly, again with no empty cell. In other words, x must be a triangular number and x + 1 must be a perfect square.

Given a and b, count how many values x + 1 with a < x + 1 < b make the game playable — that is, how many integers v with a < v < b are a perfect square whose predecessor v - 1 is a triangular number.

Input

The input consists of several test cases. Each test case is a single line containing a and b ( $0 < a < b \le 10^9$ ). The last line of the input is 0 0.

Output

For each test case, print a line

Case n: k

where k is the number of integers x + 1 with a < x + 1 < b such that the x numbered balls can be packed into a triangle (x is a triangular number) and all x + 1 balls fill an m x m square tray (x + 1 is a perfect square).

Examples2

Example 1

Input

Expected output

Case 1: 1
Case 2: 0
Case 3: 2

Example 2
Input
```
1 200
0 0
```
Expected output
```
Case 1: 3
```