Səyahət
Bir ölkədə n şəhər var, 1-dən n-ə qədər nömrələnmişdir. Səyyah əvvəlcə 1-ci şəhərdədir və ölkənin bütün şəhərlərini ziyarət etmək istəyir. O, aşağıdakı alqoritmə əsasən hərəkət edir: əvvəlcə təsadüfi olaraq [1, n-1] aralığından bir tam ədəd m seçilir. Daha sonra şəhərlər 1, 1 + m mod n, 1 + (2·m) mod n, ... ardıcıllığı ilə ziyarət edilir, artıq ziyarət edilmiş bir şəhərə çatana qədər. Qeyd edək ki, bu proses həmişə sonlu olacaq, çünki şəhərlərin sayı məhduddur. Səyyahın ölkənin bütün şəhərlərini ziyarət etmə ehtimalını tapın.
Giriş verilənləri
Giriş faylının ilk sətirində test hallarının sayı t (1 ≤ t ≤ 10000) verilir. Hər bir test bir sətirdən ibarətdir və n (2 ≤ n ≤ 2·10^9) ədədini ehtiva edir.
Çıxış verilənləri
Hər bir test üçün məsələnin cavabını ixtisar edilməmiş kəsr şəklində çıxarın.