Пусть х - действительное число. Наилучшее приближение x для знаменателя d - рациональное число r / s в приведенном виде с s ≤ d, такое, что любое рациональное число, которое ближе к x, чем r / s, имеет знаменатель, больший d:

| П / QX | <| r / sx | ⇒ q> d

Например, наилучшее приближение к √13 для значения знаменателя 20 составляет 18/5, а наилучшее приближение к √13 для знаменателя 30 - 101/28.

Найдите сумму всех знаменателей наилучших приближений к √n для знаменателя, связанного 1012, где n не является идеальным квадратом и 1 <n ≤ 100000.