#ARC094B. [ABC093D] Worst Case

[ABC093D] Worst Case

Score : 700700 points

Problem Statement

10101010^{10^{10}} participants, including Takahashi, competed in two programming contests. In each contest, all participants had distinct ranks from first through 10101010^{10^{10}}-th.

The score of a participant is the product of his/her ranks in the two contests.

Process the following QQ queries:

  • In the ii-th query, you are given two positive integers AiA_i and BiB_i. Assuming that Takahashi was ranked AiA_i-th in the first contest and BiB_i-th in the second contest, find the maximum possible number of participants whose scores are smaller than Takahashi's.

Constraints

  • 1Q1001 \leq Q \leq 100
  • 1Ai,Bi109(1iQ)1\leq A_i,B_i\leq 10^9(1\leq i\leq Q)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

QQ

A1A_1 B1B_1

::

AQA_Q BQB_Q

Output

For each query, print the maximum possible number of participants whose scores are smaller than Takahashi's.

8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323
1
12
4
11
14
57
31
671644785

Let us denote a participant who was ranked xx-th in the first contest and yy-th in the second contest as (x,y)(x,y).

In the first query, (2,1)(2,1) is a possible candidate of a participant whose score is smaller than Takahashi's. There are never two or more participants whose scores are smaller than Takahashi's, so we should print 11.