Problem Statement

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 3 < x and 5  x , the measured values are 3  (