# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Permutations and Divisors

By YouKnowWho · Limits 1s, 512 MB

Let P be a permutation of length n where each value from 1 to n occurs exactly once. A subsequence of P is called good if every element is a divisor of its immediate next element of the subsequence.

So for a permutation [2,4,1,5,3,6] of length 6, [1,3,6], , [2,6] etc are some good subsequences, where [2,3,6]—because 2 doesn’t divide 3, is not. The size of a subsequence is the number of elements in it.

We define G[n] by the maximum size of a good subsequence over all permutations of length n.

Given two integers L and R, find ## Input

The first line will contain an integer q(1 ≤ q ≤ 105), the number of queries you need to proceed.

Each of the next q lines contains two integers L and R(1 ≤ L ≤ R ≤ 109).

## Output

For each query output the value of the above function modulo (109+7).

## Sample

InputOutput
```2
1 2
3 3
```
```3
2
```

Discussion
Statistics

88% Solution Ratio

tvirussustEarliest, 1M ago