Quş ağacı
Пtiçiyə aid sonsuz binary ağacın 5 səviyyəsi aşağıdakı kimi görünür:
Bu aşağıdakı kimi müəyyən edilə bilər:
Bu, hər iki bird daxilolmasının tam (sonsuz) ağaca aid olduğu ko-rekursiv tərifdir. bird + 1 ifadəsi, ağacın hər bir kəsrinə 1 əlavə edildiyini, 1 / bird isə ağacdakı hər bir kəsrin tərsinə çevrildiyini (yəni a / b b / a olur) göstərir.
Təəccüblüdür ki, ağac hər müsbət rasional ədədi yalnız bir dəfə ehtiva edir, buna görə də hər bir sadələşdirilməmiş kəsr ağacda unikal yerdə yerləşir. Beləliklə, rasional ədədi təsvir edə bilərik, ağacda istiqamətləri (L sol alt ağac üçün, R sağ alt ağac üçün) göstərərək. Məsələn, 2 / 5 LRR kimi təqdim olunur. Verilmiş sadələşdirilməmiş kəsrə görə, ağacın zirvəsindən başlayaraq bu kəsri tapmaq üçün istiqamətləri göstərən L və R hərflərindən ibarət bir sıra çıxarın.
Giriş məlumatları
Birinci sətir testlərin sayını ehtiva edir, ən çox 100. Hər bir test bir sətirdə təqdim olunur və '/' ilə ayrılmış iki tam ədəd a və b (1 ≤ a, b ≤ 10^9) ehtiva edir. Onlar sadələşdirilməmiş kəsrin surətçisi və məxrəci kimi çıxış edir. Hər iki tam ədəd a və b 1-ə bərabər deyil və ƏBOB (a, b) = 1 şərtini ödəyir.
Hər bir test üçün istiqamətlərin sətir uzunluğu ən çox 10000 olacaq.
Çıxış məlumatları
Hər bir test üçün, bu kəsrin ptiçiyə aid ağacda yerləşməsini göstərən sətir təqdim edin.