Festival of Sticks

In the vibrant village of Stickeville, an annual tradition known as the Festival of Sticks is celebrated with great enthusiasm. Every year, villagers showcase an array of sticks, each representing a different story from their lives. However, there's a unique custom in Stickeville: it's believed that forming a triangle with three sticks brings chaos and disrupts the harmony of the festival.

According to village lore, many years ago, a triangle formation inadvertently created by three elders caused a great storm, almost washing away the village. Since that day, the elders declared that no three sticks should ever form a non-degenerate triangle during the festival to prevent any potential catastrophe.

Luna, a young villager with a mathematical mind, is tasked with a critical role this year. She's been handed sticks of various lengths, ranging from $l$ to $r$ (inclusive), and she must arrange them in a grand display. However, she must ensure that there's no subset of three distinct sticks that can form a non-degenerate triangle, maintaining the festival's harmony.

Given this responsibility, Luna needs to find out the maximum number of sticks she can display without disrupting the festival's balance. As a mathematician at heart, she's seeking a methodical way to determine the maximal size of her display, ensuring the village's safety and traditions remain intact.

Can you help Luna achieve this goal, ensuring the Festival of Sticks remains a celebration of joy and harmony?

Input

The first line contains $t$ ($1 \leq t \leq 10^6$) the number of test test cases. This is followed by the description of each test case.

Each of the next $t$ lines contains $2$ space separated integers $l$ and $r$ $(1 \leq l < r \leq 10^9)$, the lower and upper bounds of the length of the sticks.

Output

For each test case, output the maximal size of her display.

Sample

Input	Output
4 2 4 10 50 69 420 1 4	2 4 5 3
For the first test case we can see that choosing $S = \{3, 4\}$ is optimal thus $|S| = 2$.

A non-degenerate triangle is a triangle that has a positive area. For any three sticks to form a non-degenerate triangle, the sum of the lengths of the two shorter sticks must be greater than the length of the longest stick.