Bé Naot đang học cách để nội suy đa thức, kết quả nội suy thu được từ thuật toán của bé Naot là ~t~ số hữu tỉ được viết dưới dạng số ~k~-phân.

Bé Naot muốn chuyển đổi các số ~k~-phân này về các phân số dưới dạng thập phân để tiện cho việc tính toán cũng như để đạt được độ chính xác tuyệt đối. May mắn thay bé Naot đủ thông minh để nhận ra có một số số ~k~-phân trong kết quả là những số ~k~-phân vô hạn tuần hoàn, vì thế bé Naot đã viết những số ~k~-phân thu được thành một định dạng đặc biệt.

Naot sẽ viết một số ~k~-phân dưới dạng cặp xâu ~(a, b)~, trong đó:

• ~a~ là phần không vô hạn tuần hoàn, ~a~ luôn được viết dưới dạng ~d\text.e~, trong đó ~d~ là phân nguyên, ~e~ là phần ~k~-phân.

• ~b~ là phần vô hạn tuần hoàn.

• ~b~ đã được thu gọn ngắn nhất (Ví dụ: ~b = 2323~ sẽ được viết thành ~b = 23~).

Bé Naot không đủ thông minh để tìm ra số hữu tỉ từ biểu diễn ~k~-phân của nó, nhưng bé biết rằng các số hữu tỉ luôn có thể viết dưới dạng ~\frac{a}{b}~ với ~a~ và ~b~ là các số nguyên với ~b \ne 0~ và phân số đã đưa về dạng tối giản. Các bạn hãy giúp Naot của chúng ta tìm ra số hữu tỉ mà bé muốn nhé!

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ ~(t \le 100)~ là số test.

• ~t~ dòng tiếp theo, mỗi dòng gồm một số nguyên ~k~ và hai xâu ~a, b~ ~(2 \le k \le 10, 1 \le |a|, |b| \le 6)~, với cặp xâu ~(a, b)~ biểu diễn một số ~k~-phân (~|s|~ thể hiện độ dài của xâu ~s~).

Output

• In ra ~t~ dòng, dòng thứ ~i~ chứa hai số nguyên dương ~a~ và ~b~ được biểu diễn dưới dạng thập phân cho biết ~\frac{a}{b}~ là phân số tối giản biểu diễn số ~k~-phân thứ ~i~. Biết rằng đáp án luôn đảm bảo ~1 \le a, b \le 10^{18}~.

Sample Input

3
3 1.2 0
10 1.5 0
8 1.4 3

Sample Output

5 3
3 2
87 56