Mrs. Hudson hasn't made her famous pancakes for quite a while and finally she decided to make them again. She has learned m new recipes recently and she can't wait to try them. Those recipes are based on n special spices. Mrs. Hudson has these spices in the kitchen lying in jars numbered with integers from 0 to n - 1 (each spice lies in an individual jar). Each jar also has the price of the corresponding spice inscribed — some integer a i . We know three values for the i -th pancake recipe: d i , s i , c i . Here d i and c i are integers, and s i is the pattern of some integer written in the numeral system with radix d i . The pattern contains digits, Latin letters (to denote digits larger than nine) and question marks. Number x in the d i -base numeral system matches the pattern s i , if we can replace question marks in the pattern with digits and letters so that we obtain number x (leading zeroes aren't taken into consideration when performing the comparison). More formally: each question mark should be replaced by exactly one digit or exactly one letter. If after we replace all question marks we get a number with leading zeroes, we can delete these zeroes. For example, number 40A9875 in the 11 -base numeral system matches the pattern " ??4??987? ", and number 4A9875 does not. To make the pancakes by the i -th recipe, Mrs. Hudson should take all jars with numbers whose representation in the d i -base numeral system matches the pattern s i . The control number of the recipe ( z i ) is defined as the sum of number c i and the product of prices of all taken jars. More formally: (where j is all such numbers whose representation in the d i -base numeral system matches the pattern s i ). Mrs. Hudson isn't as interested in the control numbers as she is in their minimum prime divisors. Your task is: for each recipe i find the minimum prime divisor of number z i . If this divisor exceeds 100 , then you do not have to find it, print -1. The first line contains the