Rachel and Phoebe are sick of Ross trying to teach them the importance of UNAGI and decide to give him a problem to keep him busy . Ross asks for your help to solve the problem :

You are given Q queries containing two integers a,b . Your task is simple. Calculate sum of prime factors of
($a^{b^{c}}$ + 1)%m where m is $10^{6} + 3$

Input :

First line contains single integer Q .
Next Q lines contain three spaced integers a,b,c.

Output :

For each query output the answer in a new line.

Constraints :

$1 \leq Q \leq 10^{6}$

$0 \leq a,b \leq 10^{9}$

$0 \leq c \leq 10^{18}$

Problem Setter - Vaibhav Bansal