Uzaqtorpaq
Respublika Remoteland-da insanlar hər il müstəqillik günlərini qeyd edirlər. Lakin bu çox-çox uzun zaman əvvəl olduğu üçün, heç kim onun dəqiq tarixini xatırlamır. İnsanların xatırladığı yeganə şey odur ki, müstəqillikdən keçən günlərin sayı (D) mükəmməl kvadratdır və bu, n-dən kiçik və ya bərabər olan fərqli ədədlərin hasilatı kimi formalaşdırıla bilən ən böyük mümkün ədəddir.
Remoteland-da illər 1000000007 günə malik olduğuna görə, onların vətəndaşları sadəcə D-nin 1000000007-yə görə qalıqını tapmalıdırlar. Qeyd edək ki, onlar ən böyük D ilə maraqlanırlar, ən böyük D-nin 1000000007-yə görə qalıqı ilə deyil.
Giriş verilənləri
Hər bir test halı bir sətirdə bir tam ədəd n ilə təsvir olunur, (1 ≤ n ≤ 10000000). Giriş 0 olan bir sətirlə bitir.
Çıxış verilənləri
Hər bir test halı üçün Respublikanın müstəqil olduğu günlərin sayını, 1000000007-yə görə qalıqını bir sətirdə çıxış edin.