Cho số nguyên N, bạn có thể thực hiện 1 trong 4 thao tác :

1. Biến đổi N thành N / 2 nếu N chia hết cho 2

2. Biến đổi N thành N / 3 nếu N chia hết cho 3

3. Biến đổi N thành N / 5 nếu N chia hết cho 5

4. Lấy N - 1 nếu N > 1

Bạn hãy tìm số thao tác nhỏ nhất để biến đổi N thành 1

Đầu vào

• Dòng 1 là T : số bộ test

• T dòng tiếp theo mỗi dòng là số nguyên dương N

Giới hạn

• 1<=T<=100

• 1<=N<=10^9

Đầu ra

In ra đáp án của mỗi test trên từng dòng

Ví dụ :

Input 01

5
8286
1587
3779
3384
2250

Output 01

10
9
11
7
6

Cho đồ thị có hướng gồm N đỉnh và M cạnh, bạn hãy xác định xem đồ thị đã cho có chu trình âm hay không ? Nếu có hãy in ra 28tech, ngược lại in ra 29tech.

Đầu vào

• Dòng 1 bắt đầu bởi hai số nguyên N và M.

• N dòng tiếp theo, mỗi dòng gồm thông tin 1 cạnh của đồ thị

Giới hạn

• 1 ≤ N ≤ 3000

• 1 ≤ M ≤ 6000

• Trọng số là số nguyên 32bite

Đầu ra

In ra kết quả của bài toán

Ví dụ :

Input 01

7 6
1 2 1
1 3 1
1 4 1
1 5 1
6 7 -1
7 6 -1

Output 01

28tech

Cho đồ thị vô hướng gồm N đỉnh và M cạnh, bạn hãy xác định xem đồ thị có tồn tại một chu trình mà nó đi qua tất cả các cạnh của đồ thị đúng một lần hay không. Nếu có hãy in ra 28tech, ngược lại in ra 29tech.

Đầu vào

• Dòng 1 bắt đầu bởi hai số nguyên N và M.

• N dòng tiếp theo, mỗi dòng gồm thông tin 1 cạnh của đồ thị

Giới hạn

• 2 ≤ N ≤ 10^5

• 1 ≤ M ≤ 2.10^5

Đầu ra

In ra kết quả của bài toán

Ví dụ :

Input 01

6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5

Output 01

28tech

Nhân dịp nghỉ lễ ngày 2/9, Tèo muốn đi du lịch tại nước Neverland, từ thành phố Hồ Chí Minh muốn tới Neverland có tất cả M chuyến bay 1 chiều giữa các thành phố, các thành phố Tèo có thể đi qua được đánh số từ 1 tới N, trong đó thành phố Hồ Chí Minh được đánh số là 1 và Neverland được đánh số là N.

Tèo có một phiếu giảm giá ngày Quốc khánh có thể áp dụng để giảm 50% giá vé cho 1 chuyến bay duy nhất trong tất cả các chuyến bay trong hành trình tới Neverland . Nếu giá vé chuyến bay là số lẻ thì bạn sẽ được làm tròn xuống. Bạn hãy giúp Tèo sử dụng phiếu giảm giá này một cách hợp lý để có thể tối thiểu chi phí bay của Tèo. Dữ liệu đảm bảo Tèo luôn tìm được đường đi từ thành phố HCM tới Neverland.

Đầu vào

• Dòng 1 bắt đầu bởi hai số nguyên N và M.

• N dòng tiếp theo, mỗi dòng gồm thông tin x, y, z trong đó z là chi phí bay từ thành phố x tới thành phố y, đây là chuyến bay 1 chiều.

Giới hạn

• 2 ≤ N ≤ 10^5

• 1 ≤ M ≤ 2.10^5

• 1 ≤ x, y ≤ N

• 1 ≤ z ≤ 2.10^9

Đầu ra

In ra kết quả của bài toán

Ví dụ :

Input 01

10 12
1 2 4
5 7 1
4 6 4
7 9 3
9 10 1
7 8 5
1 3 1
6 7 4
4 5 1
3 4 2
8 10 5
2 4 3

Output 01

7