//{ Driver Code Starts //Initial Template for Java import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine().trim()); while(T-->0) { String str = br.readLine().trim(); Solution ob = new Solution(); int ans = ob.LongestRepeatingSubsequence(str); System.out.println(ans); } } } // } Driver Code Ends //User function Template for Java class Solution { public int LongestRepeatingSubsequence(String str) { /* Q35 dp playlist , finding Longest common subsequence in str with itself , and checking if equal characters have equal indexes or not as we need to find repeated string with different characters */ int n = str.length() ; int[][] dp = new int[n+1][n+1]; //last row ,last coloumn and last cell will be 0 by default //handling for rest of the dp for(int i = n-1 ; i>=0 ; i--){ for(int j = n-1 ; j>=0 ; j--){ //checking if chars are equal and indexes are not if(str.charAt(i) == str.charAt(j) && i!=j) dp[i][j] = dp[i+1][j+1] + 1; else dp[i][j] = Math.max(dp[i][j+1] , dp[i+1][j]); } } return dp[0][0]; } }