CP - Số chính phương
Giới hạn- Thời gian: 1.37s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
John là một người rất đam mê toán học, một lần cậu viết ra một dãy số các chữ số và nhận ra rằng dãy số vừa viết có thể tách thành một số đoạn con liên tiếp, mà mỗi đoạn con tạo thành một số là số chính phương.
Ví dụ: dãy số 149 có thể tách thành 3 đoạn: 1, 4, 9 -> mỗi đoạn đều là số chính phương hoặc có thể tách thành 2 đoạn 1 và 49.
John muốn biết là có bao nhiêu cách tách khác nhau (hai cách tách được gọi là khác nhau nếu tồn tại một vị trí tách khác nhau) dãy chữ số mình vừa viết. Điều kiện là các đoạn tách ra không bắt đầu bằng chữ số 0.
Input
- Dòng đầu là số lượng test: nTest.
- nTest dòng tiếp theo mỗi dòng ghi ra dãy chữ số mà John viết (độ dài không quá 100).
Output
- Với mỗi test ghi ra số lượng cách tìm được trên 1 dòng.
Example
Input: 1 169 Output: 2
169 -> 169 = 13^2
169 -> 16 = 4^2 và 9 = 3^2.
- Người up: dtmp