Nước Silverland sử dụng hệ thống \(100\) loại tiền xu, trong đó các xu có mệnh giá là một số chính phương từ \(1^2\) đến \(100^2\):
Với hệ thống này, để trả chính xác \(10\) xu ta có \(4\) cách:

• Trả \(10\) đồng \(1\) xu.
• Trả \(6\) đồng \(1\) xu và \(1\) đồng \(4\) xu.
• Trả \(2\) đồng \(1\) xu và \(2\) đồng \(4\) xu.
• Trả \(1\) đồng \(1\) xu và \(1\) đồng \(9\) xu.

Hãy xác định số lượng cách trả chính xác một số tiền \(m\) cho trước ở Silverland và đưa ra một cách trả phải dùng ít đồng xu nhất.

Input

• Dòng 1: số nguyên dương \(m\) \((m≤10^5 )\).

Output

• Dòng 1 : số nguyên \(k\) là số lượng cách trả, lấy phần dư khi chia cho 123456789;
• Dòng 2: số nguyên \(q\) là số đồng xu tối thiểu phải sử dụng để trả;
• Các dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(a,b\) cho biết sử dụng \(a\) đồng xu loại mệnh giá \(b^2\) trong phương án tối ưu (dùng ít đồng xu nhất).

Example

19

10
3
2 3
1 1