Магнат винодельческой империи в Мондштадте, непревзойденный во всех отношениях. Мыслитель из рыцарей Фавониуса с экзотической внешностью}.

На этот раз братья имеют дело со странным куском дерева, помеченного их именами. Этот кусок дерева можно представить в виде строки из $$$n$$$ символов. Каждый символ — это либо 'D', либо 'K'. Вы хотите сделать некоторое количество разрезов (возможно, $$$0$$$) в этой строке, разделив ее на несколько последовательных частей, каждая из которых имеет длину не менее $$$1$$$. Оба брата ведут себя достойно, поэтому они хотят разделить дерево как можно более равномерно. Они хотят знать, на какое максимальное число кусков можно разделить дерево, чтобы отношение числа символов 'D' и числа символов 'K' в каждом куске было одинаковым.

Kaeya, любознательный мыслитель, хотел бы знать решение сразу для нескольких сценариев. Он хочет узнать ответ для каждого префикса данной строки. Помогите ему решить эту задачу!

Для строки мы определяем отношение как $$$a:b$$$, где 'D' встречается в ней $$$a$$$ раз, а 'K' встречается $$$b$$$ раз. Обратите внимание, что $$$a$$$ или $$$b$$$ могут быть равны $$$0$$$, но не оба. Отношения $$$a:b$$$ и $$$c:d$$$ считаются равными тогда и только тогда, когда $$$a\cdot d = b\cdot c$$$.

Например, для строки 'DDD' отношение будет $$$3:0$$$, для 'DKD' — $$$2:1$$$, для 'DKK' — $$$1:2$$$, а для 'KKKKDD' — $$$2:4$$$. Обратите внимание, что отношения двух последних строк равны между собой, но не равны отношениям первых двух строк.