Problem Statement

Balanced Or Not? A string containing only < and > is balanced when every prefix has at least as many < as > , and the total number of < equals the total number of > . In one operation you may choose an adjacent pair >< and replace it with <> . For each test case, decide whether S can be made balanced using at most K operations. Print 1 if it can, otherwise 0 . A string that is already balanced requires 0 operations. Input Format The first line contains the number of test cases T . Each of the next T lines contains a string S and an integer K , separated by a single space. Output Format For each test case, print 1 or 0 on its own line. Constraints 1 <= T <= 1000 1 <= |S| <= 10^5 , and the sum of |S| over all test cases does not exceed 10^6 S contains only the characters < and > 0 <= K <= 10^18 Example Input 4 >< 1 >< 0 <><> 0 >><< 3 Output 1 0 1 1 Notes >< needs exactly one operation, so it s