过完年了，做一道数学题，收一下心

题目很简单，设S=1+q+q^2+q^3+q^4+......+q^n。求S mod 99991的值。

题目一共有T组测试，每组测试样例都包含两个整数n,q。

一共有T行，每行一个整数，表示所求答案

30%的数据

1<=t<=100

0<=n,q<=10^5并且数据保证n,q不同时为0

100%的数据

1<=T<=1000

0<=n,q<=5*10^7 并且数据保证n,q不同时为0