Назовем цифровой характеристикой числа n некоторую функцию f(n) такую, что:
где g(n) — сумма цифр десятичной записи числа n.
Ваня уже научился быстро вычислять цифровую характеристику для довольно больших чисел в уме, чем, собственно, и решил похвастаться перед всеми участниками BSUIR Open 2018. Участникам не слишком понравилось такое хвастовство, поэтому они предложили ему вычислить цифровую характеристику для очень большого числа, настолько большого, что записать его на бумаге не представляется возможным.
Вместо самого числа Ване предложили его описание, по которому можно восстановить это число. Описание представляет из себя четверку чисел a, b, m и k. Чтобы получить исходное число, Ване необходимо в первую очередь сгенерировать k чисел ai таких, что 
при i > 1, 
. Полученные числа ему необходимо выписать на листок бумаги в обратном порядке, таким образом получив одно большое число. Для этого числа он и должен найти цифровую характеристику.
Теперь осталось научиться проверять ответ. Напишите программу, которая по заданному описанию числа определит его цифровую характеристику.
В первой строке задано одно целое число t (1 ≤ t ≤ 10 000) — количество чисел, для которых необходимо вычислить цифровую характеристику.
В следующих t строках записаны описания чисел. Каждое описание состоит из четырех целых чисел a, b, m и k (0 ≤ a, b ≤ 109, 2 ≤ m ≤ 109 + 7, 1 ≤ k ≤ 109) — параметров генерации числа.
Гарантируется, что числа, восстановленные по каждому описанию, не содержат лидирующих нулей. Обратите внимание, что число 0 не содержит лидирующих нулей.
Выведите t строк. В каждой строке выведите ans (0 ≤ ans ≤ 9) — цифровую характеристику соответствующего числа.
4
1 1 10 5
4 5 7 8
1 2 3 4
42 42 2018 18
6
7
4
9
По первому описанию было получено число 54321. Его цифровая характеристика равна f(54321) = f(15) = f(6) = 6.
По четвертому описанию было получено число 7567146726305885465044624203783362942522101681268442.
