< На список задач
      

Задача D. Джим в ловушке и спасительная сумма

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 Mb

Вы помните, Джим отправился в далекое прошлое (примерно в 2018 год) на поиски украденных колб с энергией тессеракта. С помощью этой огромной энергии в мире снова пытается воплотиться опаснейший межвременной монстр. Джим уже вычислил место, где тот затаился, но тут неизвестный злодей сумел заманить Джима в ловушку - темное и грязное подземелье, из которого невозможно выбраться.

Нет таких людей, которым неведом страх. А смелый человек отличается именно тем, что делает свое дело, даже когда ему страшно. Джим взял себя в руки, и стал перебирать возможные пути спасения. Чтобы пересчитать возможные пути к спасению, ему хватило пальцев одной руки. Еще и лишние остались. Штук пять....

И тут он увиделна на казалось бы гладкой стальной стене небольшой кодовый замок, а рядом два числа. Джим вспомнил старинную легенду о замке в подземелье. Это был шанс на путь к спасению:

Легенда гласила следующее. Любое положительное целое число M можно разложить на сумму некоторых положительных слагаемых. И таких вариантов очень и очень много. Но если в качестве таких слагаемых рассмотрим только числа, которые являются степенями некоторого заданного числа, то количество вариантов существенно уменьшается. Например, если надо разложить число M = 5 на сумму степеней числа P = 3,то существует всего два варианта разложения:

5 = 3 + 1 + 1
5 = 1+1+1+1+1
А для M = 10 и P = 3 существует уже 5 вариантов
10 = 9 +1
10 = 3+3+3 +1
10 = 3+3+1+1+1 +1
10 = 3+1+1+1+1+1+1 +1
10 =1+1+1+1+1+1+1+1+1+1

Выход из подземелья только один - на поле ввода надо набрать единственное число - количество вариантов разложения числа M на сумму степеней числа P. Джим принялся за расчеты.

Входные данные

Входной файл содержит несколько вариантов данных и в первой строке содержит целое число N - количество таких вариантов. Каждый вариант занимает одну строку и содержит два неотрицательных целых числа - P и M. (3 ≤ P ≤ 100, 3 ≤ M ≤ 10000),

Выходные данные

В результирующий файл для каждого варианта Вы должны вывести количество вариантов записи число M в качестве суммы степеней числа P. Гарантируется, что количество вариантов поместится в целое 64-разрядную область данных

Пример входного и выходного файлов

        input.txt                 output.txt        
5 
3 9 
3 47 
5 123 
7 4321 
97 9999 
5 
63 
75 
144236 
111