one kind of inquiry:    Little Dormi picks a hub r (1≤r≤n), and the game expert will answer with an exhibit d1,d2,… ,dn, where di is the length of the most brief way from hub r to I, for all 1≤i≤n.    Furthermore, to make the game out of line challenge Little Dormi the game expert will permit

Correct answer will be upvoted else downvoted.

game expert just permits him to pose one kind of inquiry: 

Little Dormi picks a hub r (1≤r≤n), and the game expert will answer with an exhibit d1,d2,… ,dn, where di is the length of the most brief way from hub r to I, for all 1≤i≤n. 

Furthermore, to make the game out of line challenge Little Dormi the game expert will permit all things considered ⌈n2⌉ questions, where ⌈x⌉ signifies the littlest integer more noteworthy than or equivalent to x. 

Confronted with the stomach-agitating chance of not having the option to figure the tree, Little Dormi needs your assistance to devise a triumphant methodology! 

Note that the game expert makes the tree before the game beginnings, and doesn't transform it during the game. 

Input 

The principal line of input contains the integer n (2≤n≤2000), the number of hubs in the tree. 

You will then, at that point, start communication. 

Output 

At the point when your program has discovered the tree, first output a line comprising of a solitary "!" followed by n−1 lines each with two space isolated integers an and b, signifying an edge associating hubs an and b (1≤a,b≤n). Whenever you are done, end your program ordinarily following flushing the output stream.