На школьном этапе олимпиады по информатике вы решили все задачи, кроме двух самых простых. В первой задаче, вам необходимо было возвести число в некоторую степень, а во второй — представить строку в виде нескольких подряд записанных строк. Поначалу, вы подумали, что программирование это не ваше, но слегка подостыв, пришли к выводу, что нужно больше учиться! Поэтому, вы записались в Клуб Творчества Программистов, и рассказали там, о своей проблеме. В качестве работы над ошибками, преподаватель дал вам задачу, сочетающую в себе и возведение в степень, и разбиение строки на несколько подстрок. Вы конечно же решили её тогда, поэтому вам не составит труда решить её и сейчас. Вот она:

Имеется $$$n$$$ попарно различных натуральных чисел $$$p_1, \, p_2, \, \dots, \, p_n$$$ и $$$n$$$ натуральных чисел $$$c_1, \, c_2, \, \dots, \, c_n$$$.

Рассмотрим строку $$$s$$$ состоящую из цифр. Рассмотрим некоторое её разбиение на $$$k$$$ непустых подстрок: $$$s = t_1 + t_2 + \ldots + t_k$$$. Никакая $$$t_j$$$ не должна содержать ведущих нулей. Красотой подстроки $$$t_j$$$ назовем максимальное натуральное $$$y$$$, такое что $$$t_j = p_i^x$$$ и $$$y = c_i \cdot x$$$, для некоторого ($$$1 \le i \le n$$$). Если нет такого $$$i$$$, что $$$t_j = p_i^x$$$, то $$$y$$$ полагается равным $$$0$$$.

Изящностью разбиения $$$t_1, t_2, \ldots, t_k$$$ назовем минимальную красоту среди всех $$$t_j$$$.

Ваша задача найти максимально достижимую изящность, а так-же число разбиений, при которых она достижима. Дабы навсегда закрепить полученные навыки, преподаватель просил решить задачу для $$$q$$$ строк $$$s$$$.

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