Cho \(N\) xâu. Với mỗi xâu, hãy đếm số xâu khác (trong số \(N\) xâu) mà nó là tiền tố. Ví dụ, "app" là tiền tố của "apple" và "application". Hãy dùng Trie để giải.

Định dạng đầu vào

• Dòng đầu chứa \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một xâu. Tổng độ dài các xâu không quá \(10^5\).

Định dạng đầu ra

• In ra \(N\) dòng, dòng thứ \(i\) là số xâu khác mà xâu thứ \(i\) là tiền tố.

Ví dụ

Input:

4
app
apple
applet
banana

Output:

2
1
0
0

Giải thích:

• "app" là tiền tố của "apple" và "applet" → 2
• "apple" là tiền tố của... không có ai → 0? Thực tế "apple" là tiền tố của chính nó
• Đáp án chính xác: xâu i là tiền tố của các xâu khác có độ dài lớn hơn.

Ràng buộc

• 100% số điểm: Tổng độ dài \(\le 10^5\).