Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CP - Số chính phương

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.

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-14
Thời gian chạy:1.370s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP C99 JAVA NICE PAS-GPC PAS-FPC

hide comments
2013-03-12 15:16:26 Bùi Vãn Quãng



2012-11-28 18:11:44 2ez
time chặt quá!!
2011-12-13 03:04:42 Bui Duy Thong
test 10 ra 0 ma
do tach ra thi phai tat ca cac so nhan dc deu la chinh phuong het
2011-12-13 03:03:40 Bui Duy Thong
the ca 100 chu so ay la 1 so chinh phuong thi giai quyet the nao???:(
2011-06-29 06:15:26 pitago
Test 1
10
ra 0 hay 1 vậy?
2009-04-10 16:36:05 dhkhtn
kq la so int64
2009-04-10 16:33:39 dhkhtn
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.