분모 한계 $d$에서 어떤 실수 $x$의 최적 근삿값은 $s \le d$인 기약분수 형태의 유리수 $\frac r s $입니다. 이 때 $\frac r s$보다 $x$에 더 가까운 어떤 유리수가 있다면 $d$보다 큰 분모를 갖습니다:

예를 들어, 분모 한계 20에서 $\sqrt {13}$의 최적 근삿값은 $\frac {18} 5$이고 분모 한계 30에서 $\sqrt {13}$의 최적 근삿값은 $\frac {101}{28}$입니다.

$n$이 완전 제곱수가 아니고 $ 1 < n \le 100000$일 때, 분모 한계 $10^{12}$에서 $\sqrt n$의 최적 근삿값의 모든 분모의 합을 구하세요.