Description

自從佳佳從幼稚園那邊學到了「分子」和「分母」以後，就深深的愛上了分數，他認為世界上所有的有理數都應該用分數來表示。

佳佳的好朋友啾啾可不這麼認為，為了感化佳佳接受小數點的薰陶，他決定寫一些0到1之間的小數，讓佳佳練習計算小數。

可惜佳佳是個懶惰鬼，除了分數以外他什麼都不願意看，他要你這個苦命的大學生寫一個程式把啾啾給的小數全部換成他看得懂的分數。

Input Format

輸入格式如下:

輸入檔第一行: T, 代表以下有T個啾啾給的小數
第二~第T+1行: 每行有一個0~1(不包含0,1)之間的小數，可用double儲存，接著一個正整數n(範圍在1~$10^ {16}$之間)，代表佳佳能夠看懂的最大的分子和分母。

對於每個小數，幫佳佳找出一個分數，使其在他看得懂的範圍內最接近啾啾所給的小數，如果有兩個分數和給定的小數同樣接近請輸出比較小的分數。

另外，佳佳看到不是最簡分數的分數會習慣性地噁心嘔吐，希望能夠避免讓他看到這些分數。

2
0.25 10
0.4 3

1/4
1/3