При подготовке задачи по программированию было разработано $$$N$$$ решений и измерено время работы $$$T_i$$$ каждого из них на самом худшем тесте.

Специальная строка $$$S$$$ длины $$$N$$$ описывает тип каждого решения: символ $$$S_i$$$ определяет тип решения номер $$$i$$$. При этом символ 0 соответствует плохому решению, ? — спорному, а 1 — хорошему.

Тайм-лимит $$$X$$$ считается корректным, если:

• время работы всех плохих решений превышает тайм-лимит как минимум в два раза ($$$T_i \ge X \times 2$$$, если $$$S_i = 0$$$);
• время работы всех хороших решений не превышает половину тайм-лимита ($$$T_i \le X / 2$$$, если $$$S_i = 1$$$).

Время работы спорных решений не влияет на корректность тайм-лимита.

Даны $$$Q$$$ запросов, каждый из который представляет собой строку $$$S$$$ длиной $$$N$$$, описывающую тип каждого решения. Найдите для каждого запроса минимальный целый положительный тайм-лимит, который считается корректным, или определите, что это невозможно.