Problem Statement

Interactive Ruler (Hard) This is the hard version of the problem. The only difference from the easy version is that you can ask at most 7 queries. You are given a broken ruler that is missing one number x , where 2 ≤ x ≤ 999. When the ruler is used to measure a number y , it works as follows: If y < x , it returns the correct length y . If y ≥ x , it returns the incorrect length y + 1. You don't know what the missing number x is, and you need to find it. To do that, you can make queries of the form ? a b . This means you are measuring the area of a rectangle of size a × b using the broken ruler. The response will be (measured value of a ) × (measured value of b ). Your task is to find the missing number x using at most 7 queries. Input Format: There is no initial input. You should begin the interaction by asking a query. Note: Test Case 1: The judge secretly chooses the missing number x = 4. The solution first requests the area of a 3 × 5 rectangle. Since