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
1 ≤ t ≤ 1000

2 ≤ k ≤10

0 ≤ n ≤10000

SAMPLE INPUT
2
2 3
3 2

SAMPLE OUTPUT
6
4

Explanation

For sample case 1
no of nodes =15
step 1: mod=15%10->5 no of nodes=15/10->1
step 2: mod=1%10->1 no of nodes=1/10->0
since no of nodes are now 0 hence stop here
ans=5+1=6

见题面

见题面