Функция \(f(n,k)\) келесі түрде анықталады:

• Егер \(k = 0\), онда \(f(n,0)\) \(n\)-ге тең немесе одан кіші және онымен өзара жай сандардың санына тең.

• Егер \(k > 0\), онда \(f(n,k) = \sum_{d} f(d,k - 1)\), мұнда сумма \(n\) санының барлық бөлгіштері бойынша алынады.

Сізге бірнеше сұрау берілген, әрқайсысы екі бүтін сан \(n\) және \(k\) қамтиды. \(f(n, k)\)-ны \(10^9 + 7\) модулі бойынша есептеу қажет.

Енгізу

Әр тест бірнеше сұраулардан тұрады. Бірінші жолда бір бүтін сан \(t\)(\(1 \le t \le 2 \cdot 10^4\)) — сұраулардың саны. Одан кейін сұраулардың сипаттамасы беріледі.

Әр сұраудың жалғыз жолы екі бүтін сан \(n\) және \(k\) (\(1 \le n \le 10^9\), \(0 \le k \le 10^9\)) қамтиды.

Шығару

Әр сұрау үшін \(f(n, k)\)-ны \(10^9 + 7\) бөлгендегі қалдығын шығарыңыз.

Мысалдар

Енгізу 1

3
6 0
10 1
5 3

Жауап 1

2
10
7