Geeko is very happy because his exam are over so he is busy in playing games and watching movies, today he has watched lord of the rings

He got so fascinated after watching the movie that he is seeing himself in the movie in his dreams. Suddenly Gollum arrives in his dream and Ask a riddle to Geeko.

Gollum ask him about a weirdness of complete k-ary tree.

A complete k-ary tree is tree which start with a root node and at each level every node is completely filled(ie having k branches ) except at last level. Gollum ask him to find out the weirdness of the complete k-ary tree at nth level.

Note:- level is same as the levels in the classical definition of tree

Weirdness of the complete k-ary tree can be calculated as follows

Geeko has to divide number of nodes of complete k-ary tree by 10 and at each step add modulo (number of nodes%10) to the weirdness of complete k-ary tree until the number of nodes becomes 0. According to the rule he has to first perform modulo operation than division.

Geeko got stuck in the problem so he ask you programmers to give him the weirdness of the complete k-ary tree

Note root of complete k-ary is at level 0

INPUT

The first line of each test file contains a integer t denoting the number of test case.Each test case contains two numbers k and n representing the the number of branches and level of complete k-ary tree respectively

OUTPUT

for each test case output single number the Weirdness of the complete k-ary tree in new line.

CONSTRAINTS