Need help with this two number theory problems.Give me some hints please.

Problem 1:

Given an integer N <= 10^25000 find the smallest m <= N such that m/phi(m) is maximum. Where phi is euler's totient function.

Input:

The first line in the input gives the number of test cases T (T<=200), and then T lines follow each containing an integer N.

Output: Output the smallest required value of m.

Sample Input:

1
10

Output:

6

Problem 2:

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of n^k.

Input:

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n (2 ≤ n < 2^31) and k (1 ≤ k ≤ 10^7).

Output:

For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that n^k contains at least six digits.

Sample Input:

5
123456 1
123456 2
2 31
2 32
29 8751919

Sample Output:

Case 1: 123 456
Case 2: 152 936
Case 3: 214 648
Case 4: 429 296
Case 5: 665 669