Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

• There exists a pair of positive integers (a,b) such that X = 2^a \times b^2.

For example, 400 is a good integer because 400 = 2^2 \times 10^2.

Given a positive integer N, find the number of good integers between 1 and N, inclusive.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

20

Sample Output 1

5

There are five good integers between 1 and 20: 2, 4, 8, 16, and 18.
Thus, print 5.

Sample Input 2

400

Sample Output 2

24

Sample Input 3

1234567890

Sample Output 3

42413

Note that the input might not fit in a 32-bit integer type.

Problem Statement

You are given a sequence of positive integers: A=(a_1,a_2,\ldots,a_N).
You can choose and perform one of the following operations any number of times, possibly zero.

• Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 2, and replace a_i with \frac{a_i}{2}.
• Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 3, and replace a_i with \frac{a_i}{3}.

Your objective is to make A satisfy a_1=a_2=\ldots=a_N.
Find the minimum total number of times you need to perform an operation to achieve the objective. If there is no way to achieve the objective, print -1 instead.

Constraints

• 2 \leq N \leq 1000
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
1 4 3

Sample Output 1

3

Here is a way to achieve the objective in three operations, which is the minimum needed.

• Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,2,3).
• Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,1,3).
• Choose an integer i=3 such that a_i is a multiple of 3, and replace a_3 with \frac{a_3}{3}. A becomes (1,1,1).

Sample Input 2

3
2 7 6

Sample Output 2

-1

There is no way to achieve the objective.

Sample Input 3

6
1 1 1 1 1 1

Sample Output 3

0

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, \ldots, vertex N, and the i-th (1\leq i\leq M) edge connects vertices U_i and V_i.

Find the lexicographically smallest simple path from vertex X to vertex Y in G.
That is, find the lexicographically smallest among the integer sequences P=(P_1,P_2,\ldots,P_{\lvert P\rvert}) that satisfy the following conditions:

• 1\leq P_i\leq N
• If i\neq j, then P_i\neq P_j.
• P_1=X and P_{\lvert P\rvert}=Y.
• For 1\leq i\leq \lvert P\rvert-1, there exists an edge connecting vertices P_i and P_{i+1}.

One can prove that such a path always exists under the constraints of this problem.

You are given T test cases, so find the answer for each.

Constraints

• 1\leq T\leq 500
• 2\leq N\leq 1000
• N-1\leq M\leq \min\left( \frac{N(N-1)}{2},5\times 10^4\right)
• 1\leq X,Y \leq N
• X\neq Y
• 1\leq U_i<V_i \leq N
• If i\neq j, then (U_i,V_i)\neq (U_j,V_j).
• The given graph is connected.
• The sum of N over all test cases in each input is at most 1000.
• The sum of M over all test cases in each input is at most 5\times 10^4.
• All input values are integers.

Sample Input 1

2
6 10 3 5
1 2
1 3
1 5
1 6
2 4
2 5
2 6
3 4
3 5
5 6
3 2 3 2
1 3
2 3

Sample Output 1

3 1 2 5
3 2

For the first test case, graph G is as follows:

The simple paths from vertex 3 to vertex 5 on G, listed in lexicographic order, are as follows:

• (3,1,2,5)
• (3,1,2,6,5)
• (3,1,5)
• (3,1,6,2,5)
• (3,1,6,5)
• (3,4,2,1,5)
• (3,4,2,1,6,5)
• (3,4,2,5)
• (3,4,2,6,1,5)
• (3,4,2,6,5)
• (3,5)

Among these, the lexicographically smallest is (3,1,2,5), so output 3,1,2,5 separated by spaces on the first line.

For the second test case, (3,2) is the only simple path from vertex 3 to vertex 2.

Problem Statement

You are given a positive integer N.

Among all valid arithmetic expressions consisting of the characters 1, +, *, (, and ), find one of the minimum length whose value is N.

More formally, among the strings S satisfying all of the following conditions, find one of the minimum length:

• S conforms to the symbol <expr> in the BNF below.
• The value of the expression represented by S is N.

<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number>

Strings that conform to <expr> include:

• 1111+111 representing 1111+111.
• (1+1)*(1+1) representing (1+1)\times(1+1).
• (11+(1+1)*(1+1))+1 representing (11+(1+1)\times(1+1))+1.

Strings that do not conform to <expr> include:

• (1+1)(1+1)
• 1+2
• 1-1
• 1/1
• )1(
• 1++1
• +1
• (+1)
• 1*+1

Constraints

• 1 \le N \le 2000
• All input values are integers.

Sample Input 1

9

Sample Output 1

(1+1+1)*(1+1+1)

Expressions whose value is 9 include:

• (1+1+1)*(1+1+1)
• 1+1+1+1+1+1+1+1+1
• (1+1)*(1+1)*(1+1)+1

Among them, a shortest is (1+1+1)*(1+1+1).

Sample Input 2

11

Sample Output 2

11

Sample Input 3

403

Sample Output 3

1+(1+1+1)*(1+11+11+111)