Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input:  aab
Output: 1

("aa" | "b")

Example 2:

Input:  a
Output: 0

Example 3:

Input:  ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab
Output: 0

Constraints:

• 1 ≤ s.length ≤ 2000
• s consists of lowercase English letters only

Input format: A single string.

Output format: Minimum cuts.