func solve() -> Int {
    guard let input = readLine() else { return -1 }
    let str = Array(input)
    let N = str.count
    
    var isPalindrom: [[Bool]] = Array(repeating: Array(repeating: false, count: N), count: N)
    
    for len in 1...N {
        for start in 0...N-len {
            let end = start + len - 1
            
            if (len == 1) || (len == 2 && str[start] == str[end]) || (str[start] == str[end] && isPalindrom[start+1][end-1]) {
                isPalindrom[start][end] = true
            }
        }
    }

    var dp: [Int] = Array(repeating: 2501, count: N)
    
    for end in 0..<N {
        for start in 0...end {
            if isPalindrom[start][end] {
                if start == 0 {
                    dp[end] = 1
                }
                else {
                    dp[end] = min(dp[start - 1] + 1, dp[end])
                }
            }
        }
    }
    
    return dp[N-1]
}

print(solve())