Bạch và Lin đang trên đường đến quán cà phê SPIT nổi tiếng trên mạng ở đường HUSC. Nhưng vì tin tưởng nhau nên hai người đều nghĩ đối phương đã nhớ địa chỉ quán. Cuối cùng khi đến đường HUSC, cả hai nhận ra không ai nhớ địa chỉ. Bạch chỉ có ấn tượng với địa chỉ của quán như sau:

• Địa chỉ quán có dạng "Số ~a~ kiệt ~b~ đường HUSC".
• Trong đó, số nhà ~a~ bằng số kiệt ~b~ bình phương. Lin cần tổng hợp những địa chỉ thỏa mãn số nhà bằng bình phương số kiệt để chỉ đường cho Bạch, bạn hãy lập trình giúp Lin liệt kê những địa chỉ đó.

Input

• Một số nguyên ~n~ ~(1\leq n \leq 100)~ là số kiệt trên đường HUSC.

Output

• Gồm ~n~ dòng, mỗi dòng gồm hai số là số kiệt ~b~ và số nhà ~a~ cách nhau một khoảng trắng.

Samples

Sample Input

5

Sample Output

1 1
2 4
3 9
4 16
5 25