О нет, это зловещее жюри снова что-то скрывает от Вас, и Вам придется догадаться об этом интерактивно.
На этот раз вам нужно найти целое число n. Для этого вы можете задать не более 10 запросов вида "Какая k-я десятичная цифра произведения всех целых чисел от 1 до n (также известного как факториал и обозначаемого как n!)?"
Протокол взаимодействия В первой строке содержится целое число t (1≤t≤100) — количество тестов. Для каждого теста целое число n выбирается заранее. Длина n! не превышает 20000, поэтому 1≤n≤5982. Вы можете задать не более 10 запросов вида "? k
" (0≤k<20000). В ответ на запрос Вы получите одну цифру — k-ю десятичную цифру n! (ответ находится в диапазоне от 0 до 9 включительно). Цифры нумеруются с 0, начиная с наименее значимой цифры. Если n! слишком короткий, и k-ой цифры нет, то будет возвращен 0.
После того как Ваша программа найдет значение n, она должна ответить "! n
". Если ответ верный, то Вы получите "YES" и должны перейти к следующему тесту или завершить, если это был последний. Если ответ неверный, или Вы пытаетесь угадать, и существует несколько возможных ответов, согласующихся с полученной информацией, то Вы получите "NO". В этом случае Ваше решение получит вердикт "Wrong answer", и Ваш код будет немедленно завершен.