Gửi bài giải
Điểm:
0,78 (OI)
Giới hạn thời gian:
2.1s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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~ ~\rightarrow~ 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.
Sample Input
1
169
Sample Output
2
Note
~169 \rightarrow 169 = 13^2~
~169 \rightarrow 16 = 4^2~ và ~9 = 3^2~.
Bình luận