['100', '100', '1000', '10', '1', '4', '7', '1', '4', '1', '9', '2', '8', '6', '8', '10', '4', '10', '6', '10', '8', '8', '8', '5', '11', '5', '15', '2', '12', '2', '19', '3', '18', '8', '13', '8', '11', '9', '11', '9', '15', '5', '19', '3', '21', '3', '29', '8', '24', '8', '25', '9', '26', '9', '23', '10', '24', '10', '30', '6', '30', '3', '30', '3', '31', '3', '34', '4', '35', '4', '34', '7', '37', '8', '36', '9', '37', '8', '38', '2', '38', '3', '39', '3', '41', '10', '41', '10', '43', '9', '44', '9', '43', '3', '49', '3', '50', '6', '50', '8', '50', '9', '50', '8', '51', '10', '53', '7', '53', '7', '57', '8', '58', '8', '55', '8', '54', '9', '55', '10', '55', '10', '59', '8', '61', '8', '69', '8', '70', '6', '70', '6', '67', '6', '66', '2', '62', '2', '66', '2', '68', '2', '69', '4', '71', '4', '77', '6', '77', '6', '76', '6', '73', '7', '73', '7', '72', '9', '74', '9', '75', '8', '76', '8', '81', '5', '84', '7', '84', '10', '87', '9', '87', '8', '88', '5', '85', '1', '85', '1', '90', '2', '89', '2', '91', '3', '92', '3', '98', '8', '98', '6', '100', '10', '100', '9', '99', '9', '97', '8', '96', '10', '94', '11', '95', '11', '91', '13', '91', '20', '91', '13', '98', '12', '99', '17', '99', '17', '96', '18', '96', '18', '98', '21', '98', '21', '91', '22', '91', '24', '93', '28', '97', '28', '94', '30', '94', '29', '95', '29', '97', '29', '100', '31', '98', '33', '96', '31', '96', '35', '92', '35', '100', '38', '100', '37', '99', '38', '99', '38', '93', '39', '93', '41', '95', '43', '93', '47', '93', '49', '93', '43', '99', '49', '99', '49', '94', '50', '93', '50', '96', '50', '100', '51', '99', '54', '96', '57', '99', '55', '99', '52', '99', '52', '100', '55', '100', '58', '100', '58', '93', '59', '94', '61', '94', '62', '93', '66', '93', '65', '94', '63', '94', '63', '100', '64', '99', '64', '95', '67', '95', '70', '98', '71', '98', '77', '98', '77', '95', '78', '95', '74', '91', '80', '91', '80', '97', '78', '99', '80', '99', '80', '98', '81', '98', '86', '98', '84', '96', '81', '96', '84', '93', '83', '92', '85', '92', '89', '92', '87', '94', '89', '94', '91', '94', '91', '91', '92', '92', '92', '98', '94', '96', '97', '99', '99', '99', '100', '98', '98', '98', '98', '96', '92', '90', '92', '86', '96', '90', '96', '85', '99', '88', '100', '87', '96', '83', '96', '84', '93', '81', '92', '81', '92', '80', '92', '79', '91', '79', '91', '75', '92', '74', '92', '76', '96', '80', '97', '79', '97', '74', '98', '73', '98', '70', '95', '70', '95', '68', '94', '68', '92', '68', '92', '70', '91', '69', '91', '68', '91', '65', '93', '63', '96', '60', '92', '60', '93', '59', '91', '57', '91', '51', '92', '52', '100', '60', '100', '59', '93', '52', '99', '52', '97', '50', '100', '50', '100', '46', '97', '49', '96', '49', '95', '48', '95', '41', '94', '42', '94', '46', '93', '46', '93', '40', '92', '40', '92', '34', '91', '34', '92', '33', '92', '31', '96', '35', '94', '37', '97', '37', '99', '37', '99', '30', '99', '21', '91', '29', '91', '22', '92', '23', '92', '24', '92', '26', '92', '27', '93', '26', '93', '22', '95', '20', '92', '17', '95', '17', '95', '12', '93', '12', '92', '12', '94', '14', '91', '14', '92', '13', '91', '12', '93', '10', '93', '4', '95', '4', '95', '10', '100', '5', '96', '5', '96', '3', '92', '3', '92', '10', '91', '9', '90', '9', '89', '8', '86', '8', '86', '9', '84', '7', '89', '7', '86', '4', '87', '3', '86', '3', '83', '6', '80', '9', '78', '9', '78', '5', '74', '1', '74', '6', '76', '6', '77', '6', '77', '8', '71', '8', '72', '9', '70', '9', '68', '9', '68', '8', '70', '6', '67', '6', '66', '6', '63', '6', '64', '7', '65', '8', '64', '9', '60', '9', '59', '8', '57', '10', '55', '8', '59', '4', '57', '4', '54', '4', '54', '10', '51', '10', '51', '6', '50', '6', '50', '7', '48', '7', '44', '7', '44', '8', '44', '10', '42', '8', '42', '4', '44', '2', '42', '2', '40', '4', '37', '7', '35', '7', '35', '4', '36', '4', '34', '2', '32', '4', '33', '4', '32', '5', '34', '5', '30', '9', '26', '5', '29', '5', '26', '2', '26', '4', '23', '1', '23', '5', '23', '6', '23', '9', '25', '7', '25', '11', '30', '11', '30', '16', '27', '13', '27', '15', '28', '16', '28', '18', '26', '20', '26', '19', '24', '19', '24', '21', '25', '22', '26', '21', '30', '25', '26', '29', '24', '29', '25', '30', '23', '30', '22', '29', '22', '30', '23', '31', '23', '32', '28', '37', '26', '37', '24', '35', '21', '38', '25', '38', '26', '39', '26', '38', '30', '38', '27', '41', '24', '41', '24', '48', '23', '47', '22', '47', '22', '43', '22', '42', '21', '43', '21', '49', '27', '49', '27', '51', '26', '51', '25', '51', '25', '57', '24', '58', '24', '54', '21', '51', '21', '58', '22', '57', '25', '60', '24', '61', '24', '64', '24', '68', '29', '63', '30', '62', '30', '64', '29', '64', '29', '70', '27', '70', '25', '70', '26', '71', '28', '71', '28', '75', '26', '73', '26', '77', '30', '77', '30', '78', '27', '78', '27', '80', '28', '79', '31', '79', '32', '80', '32', '74', '33', '74', '34', '75', '37', '75', '36', '76', '34', '78', '35', '78', '39', '74', '41', '74', '41', '73', '41', '71', '42', '72', '42', '74', '44', '72', '43', '72', '42', '71', '46', '71', '46', '72', '51', '77', '51', '73', '54', '73', '55', '74', '55', '76', '54', '76', '56', '78', '56', '73', '59', '76', '59', '74', '61', '76', '61', '74', '65', '78', '67', '76', '69', '76', '70', '75', '63', '75', '63', '72', '62', '71', '70', '71', '71', '72', '71', '77', '79', '77', '76', '80', '77', '80', '79', '80', '79', '78', '80', '79', '80', '75', '73', '75', '73', '70', '78', '65', '72', '65', '73', '66', '73', '69', '72', '69', '72', '67', '71', '68', '71', '64', '74', '61', '73', '60', '73', '59', '74', '60', '74', '56', '73', '55', '73', '56', '71', '54', '77', '54', '77', '53', '80', '53', '77', '50', '74', '47', '77', '44', '73', '44', '73', '45', '72', '45', '72', '42', '80', '42', '79', '41', '75', '41', '75', '40', '80', '35', '79', '35', '75', '39', '71', '39', '74', '36', '71', '36', '71', '35', '71', '32', '78', '32', '78', '30', '73', '25', '73', '29', '72', '30', '72', '28', '72', '25', '72', '23', '71', '23', '71', '24', '71', '25', '70', '26', '68', '28', '66', '28', '66', '23', '63', '26', '65', '26', '65', '27', '63', '27', '64', '28', '61', '28', '60', '28', '54', '28', '54', '27', '57', '27', '57', '24', '60', '24', '59', '23', '59', '22', '51', '22', '51', '25', '50', '26', '50', '25', '46', '25', '45', '26', '42', '29', '43', '29', '49', '29', '48', '30', '46', '30', '44', '30', '45', '31', '46', '32', '44', '32', '42', '34', '44', '34', '48', '34', '50', '32', '50', '40', '47', '40', '42', '40', '43', '41', '47', '45', '50', '45', '50', '47', '50', '48', '47', '48', '42', '48', '43', '49', '42', '50', '43', '50', '43', '51', '43', '58', '46', '55', '48', '55', '48', '52', '49', '53', '49', '55', '50', '56', '50', '54', '50', '52', '51', '52', '51', '53', '52', '54', '53', '55', '54', '56', '57', '56', '57', '52', '58', '53', '58', '58', '59', '58', '59', '50', '60', '50', '55', '45', '53', '43', '53', '41', '55', '41', '54', '42', '59', '42', '60', '41', '56', '41', '57', '40', '59', '40', '60', '40', '51', '31', '53', '31', '55', '33', '59', '33', '59', '32', '60', '32', '60', '37', '61', '37', '63', '35', '66', '35', '63', '32', '62', '32', '63', '31', '69', '31', '69', '39', '69', '40', '62', '40', '63', '41', '61', '43', '61', '45', '61', '50', '68', '50', '65', '47', '70', '42', '70', '44', '69', '44', '69', '48', '69', '51', '67', '51', '64', '51', '64', '59', '64', '60', '66', '58', '65', '58', '66', '57', '67', '56', '69', '56', '69', '61', '68', '62', '68', '61', '63', '61', '63', '62', '63', '65', '66', '68', '65', '68', '61', '64', '61', '63', '60', '64', '59', '64', '54', '69', '54', '62', '56', '64', '57', '63', '60', '63', '60', '61', '52', '61', '52', '65', '50', '67', '50', '69', '45', '69', '47', '67', '43', '67', '44', '66', '42', '64', '42', '66', '41', '65', '41', '63', '40', '63', '40', '66', '36', '70', '36', '63', '36', '62', '37', '63', '37', '67', '39', '65', '39', '61', '35', '61', '36', '60', '36', '51', '35', '51', '35', '57', '32', '57', '32', '52', '34', '54', '34', '53', '33', '52', '34', '52', '32', '50', '32', '47', '40', '47', '39', '46', '32', '46', '32', '44', '32', '43', '38', '43', '38', '41', '35', '41', '35', '40', '38', '40', '38', '36', '38', '33', '37', '34', '37', '38', '31', '38', '34', '35', '38', '31', '37', '31', '38', '30', '40', '30', '32', '22', '34', '22', '35', '22', '36', '22', '36', '25', '40', '29', '40', '23', '39', '22', '37', '20', '37', '17', '37', '14', '37', '12', '40', '12', '40', '16', '38', '16', '38', '20', '39', '19', '39', '17', '41', '17', '41', '16', '44', '16', '44', '15', '46', '17', '48', '15', '48', '20', '49', '19', '50', '19', '50', '15', '51', '16', '52', '15', '53', '16', '58', '16', '55', '13', '53', '11', '55', '11', '58', '11', '60', '11', '60', '17', '61', '16', '61', '17', '61', '19', '63', '19', '63', '16', '65', '14', '61', '14', '61', '12', '63', '12', '70', '12', '71', '13', '72', '13', '73', '12', '73', '20', '80', '20', '75', '15', '76', '15', '79', '12', '79', '17', '80', '18', '81', '19', '81', '11', '85', '11', '85', '17', '87', '15', '90', '15', '90', '17', '86', '17', '85', '18', '87', '18', '84', '21', '89', '26', '89', '29', '86', '26', '85', '25', '83', '23', '83', '30', '87', '30', '87', '29', '88', '29', '88', '31', '83', '36', '83', '31', '81', '31', '81', '33', '82', '34', '82', '36', '83', '37', '82', '37', '82', '39', '82', '41', '84', '43', '87', '43', '90', '46', '90', '50', '84', '44', '84', '46', '81', '43', '81', '45', '86', '50', '87', '51', '90', '51', '89', '52', '89', '56', '82', '56', '82', '60', '85', '60', '85', '58', '86', '58', '89', '58', '86', '61', '89', '61', '86', '64', '82', '64', '82', '70', '84', '68', '89', '68', '90', '69', '90', '70', '85', '70', '84', '71', '88', '75', '86', '75', '82', '75', '82', '74', '82', '71', '81', '72', '81', '77', '83', '79', '85', '79', '85', '81', '85', '82', '90', '82', '88', '84', '86', '84', '85', '83', '83', '81', '82', '82', '83', '82', '83', '85', '80', '85', '76', '81', '76', '85', '76', '86', '77', '87', '77', '85', '78', '86', '79', '87', '78', '88', '78', '89', '70', '89', '63', '82', '62', '83', '62', '84', '64', '86', '65', '85', '67', '87', '62', '87', '63', '86', '62', '85', '60', '83', '60', '81', '54', '87', '55', '88', '56', '88', '56', '89', '55', '89', '53', '89', '53', '87', '52', '87', '50', '89', '47', '89', '42', '89', '49', '82', '48', '82', '46', '82', '45', '83', '46', '84', '41', '89', '41', '88', '40', '88', '38', '90', '38', '87', '40', '85', '39', '85', '39', '83', '37', '85', '37', '84', '31', '84', '33', '82', '30', '82', '23', '82', '30', '89', '23', '89', '22', '88', '27', '88', '24', '85', '24', '87', '23', '87', '23', '85', '20', '88', '19', '89', '19', '90', '16', '90', '13', '87', '14', '86', '17', '89', '17', '86', '16', '87', '16', '84', '16', '80', '12', '80', '12', '74', '18', '74', '18', '75', '18', '77', '18', '80', '19', '79', '20', '79', '20', '75', '15', '70', '18', '67', '18', '61', '17', '62', '16', '63', '16', '68', '12', '64', '15', '64', '15', '61', '16', '61', '16', '60', '13', '60', '11', '58', '19', '58', '20', '58', '20', '53', '18', '53', '18', '56', '13', '56', '18', '51', '19', '50', '19', '45', '16', '48', '18', '48', '18', '49', '17', '50', '15', '48', '13', '46', '13', '44', '15', '42', '17', '40', '20', '40', '20', '35', '16', '35', '18', '37', '18', '36', '19', '37', '19', '39', '16', '36', '14', '36', '14', '30', '13', '29', '19', '29', '18', '30', '19', '30', '20', '29', '20', '25', '17', '28', '17', '23', '12', '23', '15', '20', '11', '16', '13', '16', '13', '12', '12', '13', '12', '11', '13', '11', '14', '12', '14', '15', '17', '15', '17', '10', '14', '7', '12', '5', '13', '5', '20', '5', '20', '1', '19', '2', '13', '2', '12', '2', '11', '1']