After learning about Bitcoin and Dogecoin, Rar the Cat has decided to come out with his own crypto-currency -- Fishcoin.
However, Rar the Cat is sad that nobody values the Fishcoin. As such, the value of fishcoin has been relatively low. To solve this, he wants you to mine for Fishcoins in exchange for marks in this contest.
In reality, Fishcoins are actually just a string of alphanumeric characters. The alphabets can be uppercase or lowercase. To be specific, the following are the list of allowed characters to make the Fishcoin: ABCDEFGHIKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
Just like other crypto-currency, Fishcoin uses the SHA1 hash method. A valid fishcoin would be when the first K letters of the resulting hash of the Fishcoin string are exactly the same. The higher the value of K, the more valuable the particular Fishcoin is. Do note that since SHA1 only generates a hash of 40 characters, K cannot exceed 40.
For example, "q" generates a SHA1 hash of "22ea1c649c82946aa6e479e1ffd321e4a318b1b0". Since the first 2 letters are the same, "q" is a Fishcoin of value 2.
Now, Rar the Cat wants you to find the highest value Fishcoin you can find.
This is an output-only problem. You just have to submit the Fishcoin string.
To help you, there is an implementation of the SHA1 hash algorithm avaliable under attachments.
You are welcomed to use any other languages for this problem.
'Relative Scoring' will be employed for this problem.
Your score will be 100*(K/maxK)2 where maxK is the maximum K of all the submissions so far.
Due to this, the score of your submission is not fixed until the end of the contest, when all the submissions for this problem will be regraded. In order to know what is the current score of your best Fishcoin, it is advised to resubmit again periodically.