무한한 수의 손님들이 (각각 1, 2, 3, 이렇게 번호를 붙입니다) 힐베르트(Hilbert)의 최신 무한 호텔에서 방을 얻기 위해 줄 서 있습니다. 이 호텔은 무한 층이고 (각 층에 1, 2, 3, 이렇게 번호 붙입니다), 각 층에는 무한 개의 방이 (각 방도 1, 2, 3, 이렇게 번호 붙입니다) 있습니다.

처음에 호텔은 비어 있습니다. 힐베르트는 n^번째 손님에게 방을 배정하는 규칙을 정했습니다: 손님 n은 다음 중 하나의 조건을 만족하는 가장 낮은 층의 비어있는 첫 방을 배정 받습니다:

• 한 층이 비어 있음
• 비어 있지 않은 층일 때, 그 층의 최근 손님이 m이고, m + n이 완전 제곱수가 됨

손님 1은 1층이 비어 있기 때문에, 1층의 1번 방을 배정 받습니다.
손님 2는 1층의 2번 방을 받을 수 없습니다. 왜냐하면 1 + 2 = 3 이고 완전 제곱수가 아니기 때문입니다.
대신에 손님 2는 비어 있는 2층의 1번방을 배정 받습니다.
손님 3은 1층의 2번 방을 배정 받게 되는데 1 + 3 = 4 이고 완전 제곱수가 되기 때문입니다.

결국에는 줄을 선 모든 손님이 호텔에서 방을 배정 받습니다.

만일 손님 n이 f 층의 r 번방을 배정 받았다면 P(f, r) = n으로 정의합시다. 만일 어떤 손님도 배정 받지 못한 방이라면 함수 값은 0 입니다. 아래는 몇 개의 보기입니다:
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454

f × r = 71328803586048 인 모든 양의 정수 f 와 r 에 대하여 P(f, r)의 합을 구하세요. 답으로는 마지막 8자리 수를 제출하세요.