Problem Description

Kazari loves math, she has been fascinated by divisors recently.
She defines a positive integer $x$ $K$-magic if and only if there are more than $K$ integers $y$ where

* $0 < y < x$.
* $y$ has more divisors than $x$.

To show her research for those who loves math, she plans to hold an exhibition listing $K$-magic integers from small to large. Can you help her calculate the $N$-th integer in this exhibition?

Input

The first line of the input contains an integer $T$ $(1 \le T \le 10 ^ 5)$ denoting the number of test cases.
Each test case consists of one line with two integers $N, K$ $(1 \le N \le 10 ^ {18}, 0 \le K \le 233)$.

Output

For each test case, print an integer denoting the $N$-th $K$-magic integer.

3
8 0
100 100
666 233

16
387
1507