#include <bits/stdc++.h>
using namespace std;

inline int cal_step(int a, int b){
    return int(a/10 == b/10 ? 0 : 1) + int(a%10 == b%10 ? 0 : 1);
}

int modify(int num, int range){
    int res = 0, step = cal_step(num, 0);
    for(int cand = 1; cand < range; cand++){
        int step_tmp = cal_step(num, cand);
        if(step_tmp < step){
            res = cand;
            step = step_tmp;
        } else if(step_tmp == step && cand < res)
            res = cand;
    }
    return res;
}

int main(){
    int T, h, m, s;
    scanf("%d", &T);
    while(T--){
        scanf("%d:%d:%d", &h, &m, &s);
        printf("%02d:%02d:%02d\n", modify(h, 24), modify(m, 60), modify(s, 60));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int maxn = 110;
int T, m, n;
char maze[maxn][maxn];
char goal[maxn];
int goallen;
int nxt[maxn];

int search(int sx, int sy, int dx, int dy){
    int x = sx, y = sy;
    int curmat = 0;
    int res = 0;
    while(x < m && y < n){
        while(maze[x][y] != goal[curmat] && curmat)
            curmat = nxt[curmat];

        if(maze[x][y] == goal[curmat]){
            curmat = curmat + 1;
            if(curmat == goallen){
                res++;
                curmat = nxt[curmat];
            }
        }
        
        x += dx;
        y += dy;
    }
    return res;
}

	



	void build_next(){
    nxt[0] = nxt[1] = 0;
    for(int i = 2; i <= goallen; i++){
        int j = i - 1;
        while(j){
            if( goal[i-1] == goal[nxt[j]] ){
                nxt[i] = nxt[j] + 1;
                break;
            } else
                j = nxt[j];
        }
        if(goal[i-1] != goal[nxt[j]])
            nxt[i] = 0;
    }
}
                
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &m, &n);
        for(int i = 0; i < m; i++)
            scanf("%s", maze[i]);
        scanf("%s", goal);
        goallen = strlen(goal);
        build_next();
        
        int res = 0;
        for(int i = 0; i < m; i++)
            res += search(i, 0, 0, 1);
        for(int i = 0; i < n; i++)
            res += search(0, i, 1, 0);
        for(int i = 0; i < m; i++)
            res += search(i, 0, 1, 1);
        for(int i = 1; i < n; i++)
            res += search(0, i, 1, 1);
        printf("%d\n", res);
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

int T, m, n; 
int nums[maxn];

inline bool legal(int step, int start, int choice){
    if(choice == 2)
        return (nums[n - 1] - nums[start]) >= step;
    
    if(n - start < choice) return false;
    
    if(nums[start + 1] - nums[start] >= step)
        return legal(step, start + 1, choice - 1);
    
    int left = start + 1;
    int right = n - 1;
    while(right - left > 1){
        int mid = (left + right) / 2;
        if(nums[mid] - nums[start] >= step)
            right = mid;
        else
            left = mid;
    }
    return legal(step, right, choice - 1);
}


int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%d", nums + i);
        sort(nums, nums + n);
        
        int step_legal = 0;
        int step_illegal = nums[n-1] - nums[0] + 1;
        while(step_illegal - step_legal > 1){
            int mid = (step_illegal + step_legal) / 2;
            if(legal(mid, 0, m))
                step_legal = mid;
            else
                step_illegal = mid;
        }
        printf("%d\n", step_legal);
    }
    return 0;
}