F. The Tower(XVI)
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Please refer to the statements in the attachment files

Input

Please refer to the statements in the attachment files

Output

Please refer to the statements in the attachment files

Example
Input
4
1 100
2 4
74700 1
2279 1
Output
2
6
6
5
Note

Please refer to the statements in the attachment files