We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Divisor Exploration 3

Divisor Exploration 3

You are given queries where each query is in the form of three integers, , and , such that:

Using this value of along with the given , create a tree as follows :-

  • The value is the root of the tree.
  • A node is expanded such that all it's divisors are it's children.
  • Continue expanding till the tree has depth .

For example, if and , then the tree will look like the following:

image

Once the tree is built, we create another tree as follows :-

  • Every leaf node , is transformed to . Here is the totient function.
  • Every non-leaf node is equal to the sum of the values of it's children.

From our previous example tree, after constructing a new tree, we get the following tree.

image

Print the value at the root of tree after taking modulo with .

Input Format

The first line of the input contains a single integer ( ).
Following lines contain three integers given by , and .

Constraints

For points:

For Full Points:

Output Format

For each case, print the value at the root of tree modulo .

Sample Input 0

3
2 0 1
2 0 2
1 0 3

Sample Output 0

18
39
4

Explanation 0

In the first test case, the root of the divisor tree is . Root expands to level deep. So in level we have . Level contains leaves. So their special values are . So root has special value of .