Бесконечное число людей (пронумерованных 1, 2, 3, и т.д.) стоят в очереди за комнатой в новейшем бесконечном отеле Гилберта. В отеле бесконечное количество этажей (пронумерованных 1, 2, 3, и т.д.), и каждый этаж содержит бесконечное число комнат (пронумерованных 1, 2, 3, и т.д.).

Изначально отель пуст. Гилберт объявляет правило, по которому n-тый человек получает комнату: человек n получает первую свободную комнату на самом низком этаже, отвечающем хотя бы одному из следуюших условий:

• этаж пуст
• этаж не пуст и, если последний занявший на нем комнату человек имеет номер m, то m + n является квадратом целого числа

Человек 1 получает комнату 1 на этаже 1, так как он пуст.
Человек 2 не получает комнату 2 на этаже 1, так как 1 + 2 = 3 не является квадратом целого числа.
Вместо этого, человек 2 получает комнату 1 на этаже 2, так как он пуст.
Человек 3 получает комнату 2 на этаже 1, так как 1 + 3 = 4 является квадратом целого числа.

Рано или поздно, каждый человек в очереди получит свою комнату в отеле.

Пусть P(f, r) будет равно n, если человек n занял комнату r на этаже f, и равно 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

Найдите сумму всех P(f, r) для всех натуральных f и r таких, что f × r = 71328803586048, и в качестве ответа приведите последние 8 цифр полученного результата.