The floors of an index

tree databases external memory numerical precision

A database administrator estimates how many pages a search over an index will read. The index is a B-tree of minimum degree t: every page except the root has from t − 1 to 2t − 1 keys, the root from 1 to 2t − 1, a page with k keys has exactly k + 1 children if it is not a leaf, and all leaves are at the same depth. A search reads one page on each storey. How many storeys can such a tree with n keys have, in the densest case and in the sparsest?

The second test is the indexes of this catalogue: 436,069 words of “War and Peace”, 47,585 distinct words of the novel, 19,073 earthquakes from the USGS catalogue and 8966 pages of the site, with different page sizes.

Input

The first line holds q (1 ≤ q ≤ 10⁵). Each of the next q lines holds t and n (2 ≤ t ≤ 10⁹, 1 ≤ n ≤ 10¹⁸).

Output

For each line, the smallest and largest possible number of storeys separated by a space.

Examples

Example 1

Input

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

How many keys fit in a tree of L storeys if all pages are filled to the brim? And how many are needed at least for there to be L storeys?

2Hint 2

The formulas will involve logarithms, but computing logarithms in floating point will not do here: at the boundaries, where n is exactly one key short of a whole storey, rounding moves the answer by one.

3The idea

In the densest tree every page has 2t − 1 keys and 2t children, and L storeys hold (2t)^L − 1 keys; the smallest number of storeys is the smallest L for which this is at least n. In the sparsest the root has one key and two children, and the other pages t − 1 keys and t children; on L storeys that is 2t^L−1 − 1 keys, and the largest number of storeys is the largest L for which this is at most n. Both are found by trying L in integers.

4Walkthrough

The minimum of keys on L storeys: the second storey has 2 pages, the third 2t, the k-th 2t^k−2, each with t − 1 keys; together with the root's key that is 1 + 2(t − 1)(1 + t + … + t^L−2) = 2t^L−1 − 1. The maximum is the geometric series (2t − 1)(1 + 2t + … + (2t)^L−1) = (2t)^L − 1.

With n ≤ 10¹⁸ there are at most sixty storeys, so trying the values of L is instant. In Python powers are exact integers. In Go t^L quickly goes beyond uint64, so multiply with saturation: as soon as the product would exceed a cap larger than any n, take it to be the cap.

For the index of the novel's words with pages of 127 keys (t = 64) both answers are three storeys: however the pages fill up, a search will read three pages.

4+Solution

5Complexity

O(log n) per line: that many steps of trying storeys.

6Common mistakes

Floating-point logarithms. math.log(216, 6), for t = 3 and n = 215, when three full storeys are filled to the last key, gives 3.0000000000000004 instead of 3, and ceil answers 4; for n around 10¹⁸ the precision of a float is not enough at all. Tests three to five consist of such boundaries.
The root as an ordinary page. The root may hold one key; if you require t − 1 of it, the maximum height comes out lower than the real one.
Overflow in Go. 2⁶⁴ with t = 2 is reached already at the 64th storey, and (10⁹)³ does not fit in an int64.

Algorithms behind it

DS Data structure B-tree A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages. O(log n) comparisons, O(log_B n) page reads 2 problems