Hôm nay lớp của Misaki làm một vài bài tập toán. Do để quên máy tính ở nhà nên Misaki rất lúng túng trước việc phải rút gọn các căn số bậc hai. Bạn là một lập trình viên tài ba của NTUCoder, bạn hãy viết chương trình rút gọn các căn bậc hai giúp Misaki để chúng trông gọn gàng, dễ tính hơn nhé!

Yêu cầu: Cho các số N là căn số bậc hai, bạn hãy rút gọn N thành phần nguyên và căn số sao cho số trong căn là nhỏ nhất.

Dữ liệu nhập: 

  - Dòng thứ nhất chứa số T là số lượng bộ test (1 ≤ T ≤ 3000).

  - T dòng tiếp theo, mỗi dòng chứa một số N (1 ≤ N ≤ 10⁹).

Dữ liệu xuất:
  Gồm T dòng, mỗi dòng chứa 2 số nguyên là phần nguyên và phần căn đã được rút gọn.