После блестяще проведенной операции Штирлиц смог определить численность фашистской армии. Естественно такую информацию уже четыре года как ждут в штабе советской армии. Чтобы общаться со штабом Штирлиц использует \textbf{n} радистов. Каждый из радистов должен передать сообщение от Штирлица в штаб. Штирлиц, как хитрый разведчик, зашифровал свое послание таким образом: каждому из радистов он дал одно и то же число - численность армии, но в своей системе счисления, да еще так, что все основания систем счисления у радистов попарно взаимно простые. После передачи радиограммы ищейки Мюллера смогли определить последний символ каждого из сообщений. Вы работаете штатным программистом и должны определить, какое минимальное число мог послать Штирлиц в своем сообщении. Мюллер в отличие от вас не очень любит бинарный код, поэтому он хочет, чтобы искомое число вы вывели в десятичной системе. \InputFile В первой строке задается число \textbf{n} - количество радистов у Штирлица. В следующей строке находятся \textbf{n} чисел \textbf{a_i} - основания систем счисления, в которых Штирлиц давал сообщения радистам (\textbf{2} ≤ \textbf{a_i} ≤ \textbf{36} ). В третьей строке через пробел записано \textbf{n} символов \textbf{c_i} - последние буквы каждого из сообщений (\textbf{0} ≤ \textbf{c_i} < \textbf{a_i}; \textbf{c_i} - либо цифра от \textbf{0} до \textbf{9}, либо буква от \textbf{A} до \textbf{Z}). \OutputFile Вывести минимальное число, которое мог передать Штирлиц в десятичной системе счисления.