The compiler wants you to catch the exception in your test class because your store method contains 'throws InvalidRecord'.
If you want to handle the exception entirely in the store method you do not need the 'throws InvalidRecord' with your store method. You only need to specify the throws statement if you do not want to handle the exception in your method but hand it up to the calling method.
By the way, it is a convention that exceptions end with Exception --> InvalidRecordException.
Your store() method is throwing, catching, and then rethrowing the exception. First of all, you could remove the try/catch block in store() and you'd have semantically equivalent code: instead of catching the one InvalidRecord exception and creating a new one and throwing that, you'd simply be allowing the original thrown one to continue on its way.
Exceptions are virtually never used in this way: you never throw an exception and catch it in the same method. There's simply no reason to do this. And you never, ever, would catch an exception and then turn around and throw exactly the same exception again -- it accomplishes nothing except consuming an enormous amount of CPU time.
Since you don't want the caller to have to catch the InvalidRecord exception, then I don't understand why you're throwing one at all. The alternative is simply something like:
and the caller is then free to use or ignore the return value.
Essentially, the sole purpose of an exception is to send a message from some point of failure to a non-local handler. That means that if I call a method, and that method calls a method, and that method calls a method, and that method can't do what it's supposed to do, then it can throw an exception and I can catch it. Every method between me and that far-distant failing method needs to declare that it "throws FooException". When I call the "top" method, if I'm prepared for the possibility that it will fail, and it's my job to deal with the failure, then I should put in a try/catch. Otherwise, I could just declare that I, in turn, throw FooException, and let someone else handle it.
Finally, exceptions shouldn't be used to indicate expected conditions, as here; they should only be used to indicate failures and errors.