# The Preliminary Contest for ICPC Asia Nanjing 2019

### 导航

A.The beautiful values of the palace

B.super_log

F. Greedy Sequence

H.Holy Grail

### B. super_log

#### 题目

In Complexity theory, some functions are nearly O(1), but it is greater then O(1). For example, the complexity of a typical disjoint set is O(nα(n))). Here α(n) is Inverse Ackermann Function, which growth speed is very slow. So in practical application, we often assume $α(n) \le 4$.

However O(α(n)) is greater than O(1), that means if nn is large enough, α(n)α(n) can greater than any constant value.

Now your task is let another slowly function $log*x$ reach a constant value $b$. Here $log*$is iterated logarithm function, it means “the number of times the logarithm function iteratively applied on x before the result is less than logarithm base $a$”.

Formally, consider a iterated logarithm function $log_{a}^*$​

Find the minimum positive integer argument$x$, let $log_{a}^* (x) \ge b$. The answer may be very large, so just print the result x after mod m.

Input

The first line of the input is a single integer$T(T\le 300)$ indicating the number of test cases.
Each of the following lines contains 3 integers a , bb and mm.
$1 \le a \le 1000000$
$0 \le b \le 1000000$
$1 \le m \le 1000000$
Note that if a==1, we consider the minimum number x is 1.
Output

For each test case, output xx mod mm in a single line.
HintIn the 4-th query, a=3and b=2. Then$log_{3}^* (27) = 1+ log_{3}^* (3) = 2 + log_{3}^* (1)=3+(-1)=2 \ge b$, so the output is 27 mod 16 = 11.

5
2 0 3
3 1 2
3 1 100
3 2 16
5 3 233

1
1
3
11
223

### H. Holy Grail

#### 题目

As the current heir of a wizarding family with a long history, unfortunately, you find yourself forced to participate in the cruel Holy Grail War which has a reincarnation of sixty years.However,fortunately,you summoned a Caster Servant with a powerful Noble Phantasm.When your servant launch her Noble Phantasm,it will construct a magic field,which is actually a directed graph consisting of n vertices and m edges. More specifically, the graph satisfies the following restrictions :

Does not have multiple edges(for each pair of vertices x and y, there is at most one edge between this pair of vertices in the graph) and does not have self-loops(edges connecting the vertex with itself).
May have negative-weighted edges.
Does not have a negative-weighted loop.
n<=300 , m<=500.
Currently,as your servant's Master,as long as you add extra 6 edges to the graph,you will beat the other 6 masters to win the Holy Grail.

However，you are subject to the following restrictions when you add the edges to the graph:

Each time you add an edge whose cost is c,it will cost you c units of Magic Value.Therefore,you need to add an edge which has the lowest weight(it's probably that you need to add an edge which has a negative weight).
Each time you add an edge to the graph,the graph must not have negative loops,otherwise you will be engulfed by the Holy Grail you summon.

#### 说明

Σσ(・Д・；)我我我什么都没做!!!