Giải bài trực tuyến

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