과녁

Maria는 과녁 제조를 돕기 위해 Ghastly Chemicals Junkies (GCJ) 회사에 고용되었다. 과녁은 여러 개의 동심원 고리(중심이 같은 점에 있는 고리)로 이루어지며, 일반적으로 양궁 표적을 나타낸다. GCJ은 흑백 과녁을 제조하는 데 관심이 있다.

Maria는 검은색 페인트 t밀리리터로 시작하며, 이 페인트를 사용해 두께가 1cm(일 센티미터)인 고리를 그린다. 두께가 1cm인 고리는 반지름의 차이가 1cm인 두 동심원 사이의 공간이다.

Maria는 반지름이 r cm인 흰색 원 둘레에 첫 번째 검은색 고리를 그린다. 그런 다음 페인트가 충분한 동안 다음 과정을 반복한다:

• Maria는 마지막 검은색 고리 둘레에 두께가 1cm인 흰색 고리가 있다고 생각한다.

• 그런 다음 그 흰색 고리 둘레에 두께가 1cm인 새로운 검은색 고리를 그린다.

각 "흰색 고리"는 단순히 두 검은색 고리 사이의 공간이라는 점에 유의하라.

반지름이 1cm인 원판의 넓이는 π $cm^{2}$이다. 넓이 π $cm^{2}$를 칠하려면 페인트 일 밀리리터가 필요하다. Maria가 그릴 수 있는 검은색 고리의 최대 개수는 얼마인가? 다음 사항에 유의하라:

• Maria는 완전한 고리만 그린다. 남은 페인트가 완전한 검은색 고리 하나를 그리기에 충분하지 않으면 즉시 칠하기를 멈춘다.

• 적어도 검은색 고리 하나를 그릴 수 있을 만큼의 페인트가 항상 주어진다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 1000. 1 ≤ r, t ≤ 1000.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 6000. 1 ≤ r ≤ $10^{18}$. 1 ≤ t ≤ 2 × $10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 r과 t가 있는 한 줄로 이루어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이며(1부터 시작한다), y는 Maria가 그릴 수 있는 검은색 고리의 최대 개수이다.